На подвижна лента во лабораторијата на УКИМ се поставени N примероци, со меѓусебно различни висини, кои треба да се процесираат, еден по еден. За полесно да ги именуваме, ќе ги означиме со сите броеви од 1 до N, при што броевите со кои означуваме се доделени според висината на примероците, почнувајќи од 1 (за најнискиот) до N (за највисокиот).

На почеток, примероците не се подредени. Пред да се процесираат, тие мора да се подредат во растечки редослед според нивната висина. Тоа се прави со помош на механичка роботска рака. Оваа рака може да направи транспонирање, т.е. да земе одреден број на последователни примероци и да го преврти нивниот распоред (пример, ако ги земе последователните примероци 7 4 9 2, ќе ги префрли во редослед 2 9 4 7).

Алгоритамот за сортирање на примероците е следниот: Најпрвин се наоѓа локацијата L₁ на најмалиот примерок - примерокот означен со 1, и роботската рака го превртува распоредот на примероците меѓу позициите 1 и L₁. Потоа се наоѓа локацијата L₂ на примерокот 2, и роботската рака ги превртува примероците меѓу позициите 2 и L₂. Потоа се наоѓа локацијата L₃ на примерокот 3, итн...

На сликата е прикажан едноставен пример со 6 примероци. Примерок 1 се наоѓа на локација 4, па затоа роботската рака ги транспонира првите 4 примероци. Примерокот 2 се наоѓа на локација 6, па роботската рака ги транспонира примероците од 2 до 6. Во третиот чекор роботската рака ги транспонира примероците помеѓу локациите 3 и 4, бидејќи примерокот 3 се наоѓа на локација 4, итн…

За да го прави секое наредно транспонирање, роботската рака мора да знае, во моментот пред i-тото транспонирање, која е локацијата на примерокот i. Ако на влез ви е даден редоследот на примероците во нивната првична поставеност, ваша задача е да ја утврдите потребната информација за роботската рака.

Влез

Во првиот ред е даден еден број N (1 ≤ N ≤ 100 000) кој го претставува бројот на примероци кои треба да се подредат.
Вториот ред содржи N различни цели броеви: H₁, H₂, ... H_N (1 ≤ H_i ≤ N), кои ги означуваат примероците во нивната првична поставеност. За потсетување, овие броеви секогаш ќе претставуваат некаква пермутација на броевите од 1 до N.

Забелешка: За 30% од поените 1 ≤ N ≤ 1 000.

Излез

Единствената линија од излезот треба да содржи N броеви, одделени со празни места, кои ги претставуваат позициите на i-тиот примерок пред i-тото транспонирање.

Да забележиме дека за подредување на секој елемент е потребно точно едно транспонирање, односно и доколку некој примерок веќе е на својата точна позиција се смета дека се случило транспонирање на елементите од локација i до локација i.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
6
3 4 5 1 6 2

излез
4 6 4 5 6 6

влез
4
3 4 2 1

излез
4 2 4 4

Објаснување за првиот тест пример: Да забележиме дека состојбите пред првите три роботски операции се илустрирани на сликата дадена во текстот на задачата. Позицијата на 1 пред 1-вата роботска операција е 4, позицијата на 2 пред 2-рата роботска операција е 6, позицијата на 3 пред 3-тата роботска операција е 4, позицијата на 4 пред 4-тата роботска операција е 5, позицијата на 5 пред 5-тата роботска операција е 6 и позицијата на 6 пред 6-тата роботска операција е 6.