Une tour de stationnement circulaire comporte $N$ compartiments disposés en cercle. Ils sont appelés compartiment 1, compartiment 2, ..., compartiment $N$ dans le sens horaire. Chacun contient une voiture. La voiture du compartiment $i$ porte le numéro $a_i$.
La tour possède deux boutons. A la fait tourner d'un compartiment dans le sens horaire, et B d'un compartiment dans le sens antihoraire. La figure de gauche ci-dessous montre l'exemple précédent après un appui sur A, et celle de droite après un appui sur B.
On veut retirer toutes les voitures de la tour.
Les voitures ne peuvent être retirées que de l'unique compartiment tout en bas. Au départ, il s'agit du compartiment 1. Pour retirer une voiture d'un autre compartiment, il faut d'abord appuyer sur les boutons de façon à faire descendre son compartiment tout en bas.
De plus, avant de retirer une voiture portant le numéro $x$, toutes celles dont le numéro est inférieur à $x$ doivent avoir été retirées. Autrement dit, tant qu'une voiture de numéro inférieur à $x$ reste dans la tour, on ne peut pas en retirer une de numéro $x$.
Écrivez un programme calculant le nombre total minimal d'appuis sur les boutons pour retirer toutes les voitures.
Contraintes
- $1 \le N \le 100\,000$
- $1 \le a_i \le 1\,000\,000\,000$
Sous-tâches
- (8 points) $a_i=1$ ($1\le i\le N$), donc toutes les voitures portent le numéro 1.
- (9 points) $a_i\ne a_j$ si $i\ne j$, donc toutes les voitures ont des numéros distincts.
- (10 points) $N\le10$.
- (21 points) $N\le100$.
- (31 points) $N\le1\,000$.
- (21 points) Aucune contrainte supplémentaire.
Entrée
La première ligne contient un entier $N$.
La deuxième contient les numéros des voitures $a_1,\ldots,a_N$ dans l'ordre, séparés par des espaces.
Sortie
Affichez sur la première ligne le nombre total minimal d'appuis sur les boutons.
Exemples
Entrée 1
4 1 2 2 1
Sortie 1
3
Remarque
On peut procéder ainsi : retirer une voiture → bouton A → retirer une voiture → bouton A → retirer une voiture → bouton A → retirer une voiture.
Entrée 2
5 3 1 4 5 1
Sortie 2
7