Zadanie

Herkulesova trinásta úloha

Počet bodov: 60

Herkules musel vyriešiť o dosť ťažšie úlohy, ako vy tuto riešite.

Klopkanie prstami po Abakuse? To je vôbec úloha?

Na pleciach presúvať mramorové stĺpy, to je úloha.

Herkules dostal tajnú trinástu úlohu, ktorá nesmie byť zachovaná v histórií.

Pri veľkom chráme Neptúna stojí \(n\) mramorových stĺpov rôznych výšok. Nanešťastie pre Herkula ich architekti nepostavili v správnom poradí, a trebalo by ich… premiestniť.

Stĺpy sú v prijateľnom poradí, ak naľavo od stĺpu výšky \(v\) je stĺp výšky \(v-1\), s výnimkou, že naľavo od stĺpu výšky \(1\) môže byť stĺp výšky \(n\).

Herkules je síce obdarený nadľudskou silou, stĺpy sú predsa len nadľudsky ťažké. Na jedno oddýchnutie vie len dva susedné stĺpy vymeniť.

Dokážte mu, že klopkanie po Abakuse je aj na niečo dobré - zistite, koľko najmenej výmen musí Herkules vykonať, aby uspokojil Neptúna.

Úloha

Daná je permutácia čísel \(1\) až \(n\). Jednou operáciou viete vymeniť dve susedné čísla.

Zistite, koľko najmenej operácií potrebujete, aby ste dostali permutáciu v tvare \(v, v+1, \cdots, n, 1, 2 \cdots, v-1\) (prípadne \(1, \cdots, n\)).

Vstup a Výstup

V prvom riadku je číslo \(n\).

V každom z ďalších \(n\) riadkov je jedno celé číslo - výška stĺpu. Výšky stĺpov tvoria permutáciu.

Za riešenie prípadov keď \(1 \leq n \leq 100\) dostanete aspoň 10 bodov. Za riešenie prípadov keď \(1 \leq n \leq 1000\) dostanete aspoň 30 bodov. Za riešenie prípadov keď \(1 \leq n \leq 10^5\) dostanete plný počet bodov.

Vypíšte jedno číslo - najmenší možný počet výmen, ako popísané v úlohe.

Príklad

Input:

6
3
5
6
4
2
1

Output:

3

3 5 6 4 2 1 -> 3 5 4 6 2 1 -> 3 4 5 6 2 1 -> 3 4 5 6 1 2