Bartek er en kjent technomusikkprodusent, og han finpusser for tiden sin neste hit. Han har laget et spor bestående av $n$ taktslag (beats), nummerert fortløpende fra $1$ til $n$. Etter å ha brukt timer i et musikkredigeringsprogram skulle han akkurat til å eksportere mp3-filen, men han la merke til at taktslagene for øyeblikket er ordnet i rekkefølgen $a_1, a_2, \dots, a_n$. Bartek må oppnå en stigende rekkefølge på taktslagene, det vil si $1, 2, \dots, n$.

Programmet tillater to typer operasjoner:

• Flytt det siste taktslaget til en hvilken som helst posisjon, f.eks. $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Flytt et hvilket som helst taktslag til begynnelsen, f.eks. $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Hva er det minste antall operasjoner som trengs for å ordne taktslagene i stigende rekkefølge?

Inndata

Den første linjen inneholder et heltall $n$ ($1 \le n \le 200\,000$), som angir antall taktslag.

Den andre linjen inneholder $n$ parvis forskjellige heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), som representerer den nåværende rekkefølgen av taktslag i programmet.

Utdata

Skriv ut ett enkelt heltall – det minste antallet operasjoner som kreves.

Eksempler

Inndata 1

6
3 2 5 4 1 6

Utdata 1

4

Inndata 2

9
3 1 2 5 6 4 9 7 8

Utdata 2

6

Merk

Vi starter med sekvensen av taktslag $(3, 2, 5, 4, 1, 6)$. Her er én måte å oppnå ønsket rekkefølge på i fire operasjoner:

• Flytt det siste taktslaget to plasser til venstre: $(3, 2, 5, \underline{6}, 4, 1)$.
• Flytt taktslag $2$ til begynnelsen: $(\underline{2}, 3, 5, 6, 4, 1)$.
• Flytt taktslag $1$ til begynnelsen: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Flytt det siste taktslaget to plasser til venstre: $(1, 2, 3, \underline{4}, 5, 6)$.

Det er mulig å oppnå en stigende rekkefølge på andre måter ved hjelp av fire operasjoner, men det kan ikke gjøres på tre operasjoner, så resultatet er $4$.