V poslednej dobe sa medzi vedúcimi KSP (a možno aj riešiteľmi, ktovie?) šíri istý nepekný nešvár. Často sa zrazu, len tak, z ničoho nič rozhodnú, že si idú nejako meniť hardvér svojho počítača.

Aj Maťo padol za obeť tomuto nešťastnému trendu, a skončilo to odpadnutým rámom displeja na jeho notebooku. Teraz musí zháňať nový. Našiel však na internete strašne veľa predajných ponúk a v kartách prehliadača má trošku bordel, a navyše ich je toľko, že nevidí, čo v nich je¹. Preto ich vie usporiadavať iba tak, že práve otvorenú kartu posunie buď na začiatok alebo na koniec.

Úloha

Na vstupe dostanete pole $n$ čísel od $1$ po $n$ v náhodnom poradí, ktoré predstavujú ceny nových rámov. Môžete ich usporiadať iba presúvaním prvkov na začiatok alebo na koniec. Vašou úlohou je usporiadať ich s čo najmenším počtom krokov.

Formát vstupu

V prvom riadku vstupu je číslo $n$ ($0 \leq n \leq 10^6$) udávajúce počet čísel v poli.

V druhom riadku vstupu je $n$ rôznych čísel oddelených medzerou ($1 \leq a_i \leq n$). Konkrétne sú to čísla od $1$ do $n$, v náhodnom poradí.

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo udávajúce najmenší možný počet krokov potrebných na usporiadanie poľa.

Príklady

7
2 6 1 5 3 4 7

4

1. krok: presunieme jednotku na začiatok (1 2 6 5 3 4 7)

2. krok: presunieme päťku na koniec (1 2 6 3 4 7 5)

3. krok: presunieme šestku na koniec (1 2 3 4 7 5 6)

4. krok: presunieme sedmičku na koniec (1 2 3 4 5 6 7)

5
1 2 3 4 5

0

Pole už je usporiadané, takže potrebujeme 0 krokov.