3. Korman je gurmán

Máme tu ďalší problém. Andrej má narodeniny a k nim dostal veľký počet darčekov. Keďže si vždy na narodeniny prial len a len veľkú sladkú čokoládu a mamka už nemohla počúvať to jeho večné fňukanie, tak sa rozhodla, že mu kúpi tú najväčšiu, akú v meste majú.

Mamka si myslela, že čokoláda všetko vyrieši a bude pokoj. Ale nevyriešila. Andrej je gurmán a jeho gurmánske požiadavky sú známe už v ďalekej Číne, možno aj ďalej. Andrej jednoducho nemôže zjesť čokoládu ako normálny človek. On si čokoládu rozdelil na kocky, kde každá kocka má svoju sladkosť. Tieto kocky následne uložil do jedného dlhého radu na stole.

Andrej chce teraz zjesť všetky kocky zaradom zľava doprava. Pritom chce, aby každá ďalšia kocka, ktorú zje, bola sladšia alebo rovnako sladká ako predchádzajúca. Andrej je ešte k tomu veľmi lenivý a jediné, čo vie spraviť, je zobrať nejakú kocku čokolády a dať ju na začiatok radu. S touto požiadavkou šiel k mamke, aby mu povedala, koľko preložení treba urobiť, aby boli kocky usporiadané. Lenže mamka ho už má plné zuby a keďže nevedela čo spraviť, zavolala na linku prvej pomoci KSP a žiadá vás o pomoc.

Úloha

Na vstupe máte číslo \(n\) a pole čísel veľkosti \(n\). Vašou úlohou je vypočitať, koľko najmenej operácií je potrebných na usporiadanie poľa od najmenšieho čísla po najvačšie. Jediná operácia, ktorú máte povolenú, je zobrať nejaké čislo v poli a preložiť ho na začiatok. Zaujíma nás len počet týchto preložení.

Formát vstupu

Na prvom riadku vstupu sa nachádza celé číslo \(n\) (\(1 \leq n \leq 1\,000\,000\)) – počet kociek čokolády. Na druhom riadku sa nachádza \(n\) čísel \(s_1, s_2, \dots s_n\), kde \(s_i\) označuje sladkosť \(i\)-tej kocky. Pre každé \(i\) platí \(0 \leq s_i \leq 10^9\).

Vaše riešenie otestujeme na štyroch testovacích sadách. V prvých dvoch sadách máte zaručené, že na vstupe sa budú vždy nachádzať čísla od \(1\) po \(n\), každé práve raz. Za riešenie, ktoré vyrieši takúto podúlohu, viete získať až polovicu bodov.

Formát výstupu

Na jediný riadok výstupu vypíšte najmenší možný počet preložení potrebných na to, aby boli kocky usporiadané od najmenej sladkej po najsladšiu. Výstup ukončite znakom nového riadku.

Príklady

Input:

5
5 1 2 3 4

Output:

4

Najprv preložíme na začiatok kocku so sladkosťou 4. Potom kocku so sladkosťou 3, potom 2, a nakoniec 1. Urobili sme 4 preloženia.

Input:

6
1 1 1 1 1 1

Output:

0

V tomto prípade netreba prekladať nič.

Input:

10 
1 5 6 50 12 3 499 5000001 3 3

Output:

7