Bartek är en välkänd technomusikproducent, och han håller just nu på att finslipa sin nästa hit. Han har skapat ett spår som består av $n$ taktslag (beats), numrerade i följd från $1$ till $n$. Efter att ha tillbringat timmar i ett musikredigeringsprogram skulle han precis exportera mp3-filen, men han märkte att taktslagen för närvarande ligger i ordningen $a_1, a_2, \dots, a_n$. Bartek behöver få en stigande ordning på taktslagen, det vill säga $1, 2, \dots, n$.

Programmet tillåter två typer av operationer:

• Flytta det sista taktslaget till valfri position, t.ex. $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Flytta valfritt taktslag till början, t.ex. $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Vilket är det minsta antalet operationer som behövs för att ordna taktslagen i stigande ordning?

Indata

Den första raden innehåller ett heltal $n$ ($1 \le n \le 200\,000$), som anger antalet taktslag.

Den andra raden innehåller $n$ parvis olika heltal $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), som representerar den nuvarande ordningen av taktslagen i programmet.

Utdata

Skriv ut ett enda heltal – det minsta antalet operationer som krävs.

Exempel

Indata 1

6
3 2 5 4 1 6

Utdata 1

4

Indata 2

9
3 1 2 5 6 4 9 7 8

Utdata 2

6

Anmärkning

Vi börjar med sekvensen av taktslag $(3, 2, 5, 4, 1, 6)$. Här är ett sätt att uppnå den önskade ordningen på fyra operationer:

• Flytta det sista taktslaget två steg åt vänster: $(3, 2, 5, \underline{6}, 4, 1)$.
• Flytta taktslag $2$ till början: $(\underline{2}, 3, 5, 6, 4, 1)$.
• Flytta taktslag $1$ till början: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Flytta det sista taktslaget två steg åt vänster: $(1, 2, 3, \underline{4}, 5, 6)$.

Det är möjligt att få en stigande ordning på andra sätt med fyra operationer, men det går inte att göra på tre operationer, så resultatet är $4$.