Pis Treap

Treap, dekart ağacı olaraq da bilinən, ikili axtarış ağacında açar dəstini saxlayan bir məlumat strukturudur.

Hər bir ağacın zirvəsi $(x,y)$ cütü ilə təyin olunur.

Zirvələrin $x$ dəyərləri saxlanılan açarların dəyərləridir və "ikili axtarış ağacı" qaydasına uyğun gəlir: sol alt ağacın bütün $x$ dəyərləri kökdəki $x$ dəyərindən kiçik, sağ alt ağacın bütün $x$ dəyərləri isə kökdəki $x$ dəyərindən böyükdür.

Zirvələrin $y$ dəyərləri isə "yığın" qaydasına uyğun gəlir: zirvənin $y$ dəyəri valideynin $y$ dəyərindən kiçik və ya bərabərdir.

Hər yaradılan düyün üçün $y$ dəyəri adətən müəyyən bir paylanmaya uyğun olaraq təsadüfi seçilir ki, bu da bir çox əməliyyatların yaxşı orta vaxt mürəkkəbliyinə səbəb olur.

Bu məlumat strukturu ikili axtarış ağacı və yığının bəzi xüsusiyyətlərini birləşdirdiyi üçün onun adı "portmanteau" terminidir, iki sözün birləşməsindən ibarətdir: TRee + hEAP = TREAP.

Benjamin, $y$ dəyərinin seçilməsi prosedurundakı qeyri-müəyyənliyin pis olduğunu düşündü, çünki bu halda sorğuların icra müddəti fərqli olur. O, hər düyün üçün $y$ dəyərini onun $x$ dəyərinə əsasən müəyyənləşdirməyə qərar verdi. O, $y=sin(x)$ qaydasını seçdi. Benjamin xüsusilə sevinir ki, müxtəlif tam ədədlər $x$ həmişə müxtəlif $y$ verəcəkdir.

Barbara başa düşür ki, qeyri-müəyyən dekart ağacı "pis" təsadüfi ardıcıllıq verildikdə ən pis performansı göstərsə də, müəyyən dekart ağacı "pis" açar dəsti verildikdə ən pis performansı göstərir. O, bunu Benjamina izah etmək istəyir və ona $n$ tam ədəd açarları göstərmək istəyir ki, onlar onun məlumat strukturunda saxlanıldıqda, hündürlüyü $n$ olan ağac formalaşsın — mümkün olan ən "tarazsız" vəziyyət.

Barbaraya belə $n$ açarları təmin etməkdə kömək edin. Bu açarların hamısı $32$ - bitlik işarəli tipə uyğun olmalıdır.

Giriş verilənləri

Bir tam ədəd $n(1\le n\le 50000)$.

Çıxış verilənləri

Fərqli tam ədəd açarları ehtiva edən $n$ sıra çıxarın. Bütün açarlar $-2^{31}$ və $2^{31}-1$ daxil olmaqla intervalda olmalıdır. $y=sin(x)$ qaydasına əsasən açarlarda qurulan dekart ağacı hündürlüyü $n$ olmalıdır.

Nümunələr