Bartek est un producteur de musique techno bien connu, et il peaufine actuellement son prochain tube. Il a créé une piste composée de $n$ temps (beats), numérotés consécutivement de $1$ à $n$. Après avoir passé des heures sur un logiciel d'édition musicale, il était sur le point d'exporter le fichier mp3 lorsqu'il a remarqué que les temps sont actuellement disposés dans l'ordre $a_1, a_2, \dots, a_n$. Bartek doit obtenir un ordre croissant des temps, c'est-à-dire $1, 2, \dots, n$.

Le logiciel permet deux types d'opérations :

• Déplacer le dernier temps vers n'importe quelle position, par ex. $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Déplacer n'importe quel temps au tout début, par ex. $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Quel est le nombre minimal d'opérations nécessaires pour ranger les temps par ordre croissant ?

Entrée

La première ligne contient un entier $n$ ($1 \le n \le 200\,000$), désignant le nombre de temps.

La deuxième ligne contient $n$ entiers deux à deux distincts $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), représentant l'ordre actuel des temps dans le logiciel.

Sortie

Affichez un seul entier – le nombre minimal d'opérations requises.

Exemples

Entrée 1

6
3 2 5 4 1 6

Sortie 1

4

Entrée 2

9
3 1 2 5 6 4 9 7 8

Sortie 2

6

Note

Nous partons de la séquence de temps $(3, 2, 5, 4, 1, 6)$. Voici une façon d'obtenir l'ordre souhaité en quatre opérations :

• Déplacer le dernier temps de deux positions vers la gauche : $(3, 2, 5, \underline{6}, 4, 1)$.
• Déplacer le temps $2$ au début : $(\underline{2}, 3, 5, 6, 4, 1)$.
• Déplacer le temps $1$ au début : $(\underline{1}, 2, 3, 5, 6, 4)$.
• Déplacer le dernier temps de deux positions vers la gauche : $(1, 2, 3, \underline{4}, 5, 6)$.

Il est possible d'obtenir un ordre croissant d'autres manières en quatre opérations, mais cela ne peut pas être fait en trois opérations, le résultat est donc $4$.