AlanashKO uwielbia pieniądze. W przeddzień Nowego Roku otrzymał $N$ banknotów. Nominał każdego banknotu jest dodatnią liczbą całkowitą. Podczas zabawy AlanashKO ułożył wszystkie banknoty w rzędzie i ponumerował je od lewej do prawej od $1$ do $N$. Następnie postanowił uporządkować wszystkie banknoty niemalejąco.

W tym celu AlanashKO wykonuje następującą procedurę: najpierw dzieli banknoty na jeden lub więcej rozłącznych spójnych fragmentów, przy czym każdy banknot należy do pewnego fragmentu. Następnie wszystkie fragmenty, w kolejności od lewej do prawej, wstawia po kolei do nowego rzędu, tzn. najpierw wstawia skrajny lewy fragment (pierwszy fragment), potem kolejny od lewej i tak dalej. Każdy fragment wstawia między dowolne dwa banknoty albo na jednym z dwóch końców aktualnego nowego rzędu. Kolejność banknotów wewnątrz fragmentu nie zmienia się podczas wstawiania.

AlanashKO chce zminimalizować liczbę fragmentów, tak aby ostatecznie mógł uporządkować banknoty niemalejąco. Pomóż mu wyznaczyć tę wartość.

Wejście

Pierwszy wiersz zawiera jedną dodatnią liczbę całkowitą $N$ ($1 \le N \le 10^6$) — liczbę banknotów. Następny wiersz zawiera $N$ dodatnich liczb całkowitych $a_i$ ($1 \le a_i \le 10^6$) — nominał $i$-tego banknotu.

Wyjście

W jednym wierszu wypisz jedną liczbę całkowitą — minimalną liczbę fragmentów pozwalającą AlanashKO uporządkować banknoty.

Podzadania

To zadanie obejmuje cztery podzadania:

1. $N \le 8$. Warte 9 punktów.
2. $N \le 20$. Warte 16 punktów.
3. $N \le 300$. Warte 20 punktów.
4. $N \le 10^6$. Warte 55 punktów.

Punkty za każde podzadanie zostaną przyznane tylko wtedy, gdy rozwiązanie pomyślnie przejdzie wszystkie wcześniejsze podzadania.

Przykład

Wejście 1

6
3 6 4 5 1 2

Wyjście 1

3

Uwagi

Fragment jest spójnym podciągiem.

Rozważmy przykład:

Minimalną odpowiedź daje podział na 3 fragmenty: |3 6|4 5|1 2| (kreski oznaczają granice fragmentów).

Po pierwszym kroku: początkowy rząd to |4 5|1 2|, a nowy rząd to |3 6|.

W drugim kroku fragment |4 5| zostaje wstawiony między $3$ i $6$.

Po drugim kroku: początkowy rząd to |1 2|, a nowy rząd to |3 4 5 6|.

Następnie fragment |1 2| zostaje wstawiony na początku nowego rzędu, dając wynik |1 2 3 4 5 6|.