Istnieje okrągła wieża parkingowa z $N$ przedziałami rozmieszczonymi na okręgu. Nazywamy je kolejno przedziałami 1, 2, ..., $N$, zgodnie z ruchem wskazówek zegara. Każdy zawiera jeden samochód. Samochód w przedziale $i$ ma numer $a_i$.

Wieża ma dwa przyciski. Przycisk A obraca ją o jeden przedział zgodnie z ruchem wskazówek zegara, a B — przeciwnie. Lewy rysunek poniżej pokazuje stan z powyższego przykładu po naciśnięciu A, a prawy po naciśnięciu B.

Chcemy usunąć z wieży wszystkie samochody.

Samochód można usunąć tylko z jednego przedziału na samym dole. Początkowo na dole znajduje się przedział 1. Aby usunąć samochód z innego przedziału, trzeba najpierw odpowiednio naciskać przyciski i obrócić jego przedział na dół.

Ponadto przed usunięciem samochodu o numerze $x$ trzeba usunąć wszystkie samochody o mniejszych numerach. Innymi słowy, jeśli w wieży pozostał samochód o numerze mniejszym od $x$, nie można usunąć samochodu o numerze $x$.

Napisz program znajdujący najmniejszą łączną liczbę naciśnięć przycisków potrzebną do usunięcia wszystkich samochodów.

Ograniczenia

• $1 \le N \le 100\,000$
• $1 \le a_i \le 1\,000\,000\,000$

Podzadania

1. (8 punktów) $a_i=1$ ($1\le i\le N$), czyli wszystkie samochody mają numer 1.
2. (9 punktów) $a_i\ne a_j$, gdy $i\ne j$, czyli wszystkie samochody mają różne numery.
3. (10 punktów) $N\le10$.
4. (21 punktów) $N\le100$.
5. (31 punktów) $N\le1\,000$.
6. (21 punktów) Brak dodatkowych ograniczeń.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $N$.

Drugi zawiera numery samochodów $a_1,\ldots,a_N$ w kolejności, oddzielone spacjami.

Wyjście

W pierwszym wierszu wypisz najmniejszą łączną liczbę naciśnięć przycisków.

Przykład

Wejście 1

4
1 2 2 1

Wyjście 1

3

Uwagi

Można wykonać kolejno: usuń samochód → przycisk A → usuń samochód → przycisk A → usuń samochód → przycisk A → usuń samochód.

Wejście 2

5
3 1 4 5 1

Wyjście 2

7