Bartek on tunnettu teknomusiikin tuottaja, ja hän viimeistelee parhaillaan seuraavaa hittiään. Hän on luonut kappaleen, joka koostuu $n$ iskusta (biitistä), jotka on numeroitu peräkkäin $1$:stä $n$:ään. Vietettyään tuntikausia musiikinmuokkausohjelmassa hän oli juuri viemässä mp3-tiedostoa, mutta huomasi, että biitit ovat tällä hetkellä järjestyksessä $a_1, a_2, \dots, a_n$. Bartekin täytyy saada biitit nousevaan järjestykseen, eli $1, 2, \dots, n$.

Ohjelma sallii kahdenlaisia operaatioita:

• Siirrä viimeinen biitti mihin tahansa kohtaan, esim. $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Siirrä mikä tahansa biitti alkuun, esim. $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Mikä on pienin mahdollinen operaatioiden määrä, joka tarvitaan biittien järjestämiseen nousevaan järjestykseen?

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 200\,000$), joka ilmaisee biittien lukumäärän.

Toinen rivi sisältää $n$ pareittain erisuurta kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), jotka kuvaavat biittien nykyistä järjestystä ohjelmassa.

Tuloste

Tulosta yksi kokonaisluku – tarvittavien operaatioiden vähimmäismäärä.

Esimerkit

Syöte 1

6
3 2 5 4 1 6

Tuloste 1

4

Syöte 2

9
3 1 2 5 6 4 9 7 8

Tuloste 2

6

Huomautus

Aloitamme biittijonosta $(3, 2, 5, 4, 1, 6)$. Tässä on yksi tapa saavuttaa haluttu järjestys neljällä operaatiolla:

• Siirrä viimeinen biitti kaksi paikkaa vasemmalle: $(3, 2, 5, \underline{6}, 4, 1)$.
• Siirrä biitti $2$ alkuun: $(\underline{2}, 3, 5, 6, 4, 1)$.
• Siirrä biitti $1$ alkuun: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Siirrä viimeinen biitti kaksi paikkaa vasemmalle: $(1, 2, 3, \underline{4}, 5, 6)$.

Nouseva järjestys on mahdollista saavuttaa muillakin tavoilla neljällä operaatiolla, mutta sitä ei voida tehdä kolmella operaatiolla, joten tulos on $4$.