SPOJ in Armenian

Երկուական փնտրման ծառը փնտրում կատարելու համար արդյունավետ տվյալների կառուցվածք է։ Երկուական փնտրման ծառում ձախ ենթածառի բոլոր տարրերի արժեքները ավելի փոքր են, իսկ աջ ենթածառի բոլոր տարրերի արժեքները ավելի մեծ են արմատի արժեքից։ Երկուական փնտրման ծառերի մասին կարող եք կարդալ այստեղ.

http://en.wikipedia.org/wiki/Binary_search_tree

Սովորաբար երկուական փնտրման ծառը կառուցվում է հաջորդաբար տարրեր ավելացվելով։ Այդ դեպքում ծառի կառուցվածքը կախված է ավելացվող տարրերի հերթականությունից։

Այս խնդրում պահանջվում է գտնել 1-ից N թվերի այնպիսի հերթականություն, որ նրանցից կառուցված ծառի բարձրությունը լինի առավելագույնը H։ Երկուական փնտրման ծառի բարձրությունը սահմանվում է հետևյալ կերպ.

1.      Հանգույց չունեցող երկուական փնտրման ծառի բարձրությունը 0 է։

2.     հակառակ դեպքում այն հավասար է ձախ ենթածառի և աջ ենթածառի բարձրություններից մեծագույնին գումարած 1։

Մի քանի դասավորություններ կարող են բավարարել այս պայմանին։ Այդ դեպքում պետք է ընտրել այն դասավորությունը, որում ավելի փոքր թվերը ավելի շուտ են գալիս։ Օրինակ, N=4, H=3 դեպքում նախընտրում ենք 1 3 2 4 հաջորդականությունը, այլ ոչ թե 2 1 4 3-ը կամ 3 2 1 4-ը։

Մուտքը.

Մուտքում տրված է երկու ամբողջ թիվ՝ N(1≤N≤10000) և H (1≤H≤30):

Ելքը.

Ելքի միակ տողում տողում պետք է արտածել N ամբողջ թվեր։ Տողի վերջում բացակ չպիտի լինի։ Եթե հնարավոր չէ կառուցել այդպիսի ծառ, հարկավոր է արտածել “Impossible.”

Օրինակներ

Մուտքը.
6 3

Ելքը.
3 1 2 5 4 6

Մուտքը.
4 1

Ելքը.
Impossible.