Bartek è un noto produttore di musica techno e attualmente sta perfezionando la sua prossima hit. Ha creato una traccia composta da $n$ battiti (beat), numerati consecutivamente da $1$ a $n$. Dopo aver trascorso ore su un programma di editing musicale, stava per esportare il file mp3, ma ha notato che i battiti sono attualmente disposti nell'ordine $a_1, a_2, \dots, a_n$. Bartek deve ottenere un ordine crescente dei battiti, vale a dire $1, 2, \dots, n$.

Il programma consente due tipi di operazioni:

• Spostare l'ultimo battito in qualsiasi posizione, ad es. $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Spostare qualsiasi battito all'inizio, ad es. $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Qual è il numero minimo di operazioni necessarie per disporre i battiti in ordine crescente?

Input

La prima riga contiene un intero $n$ ($1 \le n \le 200\,000$), che indica il numero di battiti.

La seconda riga contiene $n$ interi a due a due distinti $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), che rappresentano l'ordine attuale dei battiti nel programma.

Output

Stampa un singolo intero – il numero minimo di operazioni richieste.

Esempi

Input 1

6
3 2 5 4 1 6

Output 1

4

Input 2

9
3 1 2 5 6 4 9 7 8

Output 2

6

Note

Iniziamo con la sequenza di battiti $(3, 2, 5, 4, 1, 6)$. Ecco un modo per ottenere l'ordine desiderato in quattro operazioni:

• Spostare l'ultimo battito di due posizioni a sinistra: $(3, 2, 5, \underline{6}, 4, 1)$.
• Spostare il battito $2$ all'inizio: $(\underline{2}, 3, 5, 6, 4, 1)$.
• Spostare il battito $1$ all'inizio: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Spostare l'ultimo battito di due posizioni a sinistra: $(1, 2, 3, \underline{4}, 5, 6)$.

È possibile ottenere un ordine crescente in altri modi usando quattro operazioni, ma non è possibile farlo in tre operazioni, quindi il risultato è $4$.