Bartek jest znanym producentem muzyki techno i obecnie dopracowuje swój kolejny przebój. Stworzył utwór składający się z $n$ bitów, ponumerowanych kolejno od $1$ do $n$. Po spędzeniu wielu godzin w programie do edycji muzyki miał już wyeksportować plik mp3, ale zauważył, że bity są obecnie ułożone w kolejności $a_1, a_2, \dots, a_n$. Bartek musi uzyskać rosnącą kolejność bitów, to znaczy $1, 2, \dots, n$.

Program pozwala na dwa rodzaje operacji:

• Przeniesienie ostatniego bitu na dowolną pozycję, np. $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Przeniesienie dowolnego bitu na początek, np. $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Jaka jest minimalna liczba operacji potrzebnych do ułożenia bitów w kolejności rosnącej?

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 200\,000$), oznaczającą liczbę bitów.

Drugi wiersz zawiera $n$ parami różnych liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), reprezentujących obecną kolejność bitów w programie.

Wyjście

Wypisz jedną liczbę całkowitą – minimalną wymaganą liczbę operacji.

Przykłady

Wejście 1

6
3 2 5 4 1 6

Wyjście 1

4

Wejście 2

9
3 1 2 5 6 4 9 7 8

Wyjście 2

6

Uwaga

Zaczynamy od ciągu bitów $(3, 2, 5, 4, 1, 6)$. Oto jeden ze sposobów uzyskania pożądanej kolejności w czterech operacjach:

• Przenieś ostatni bit o dwa miejsca w lewo: $(3, 2, 5, \underline{6}, 4, 1)$.
• Przenieś bit $2$ na początek: $(\underline{2}, 3, 5, 6, 4, 1)$.
• Przenieś bit $1$ na początek: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Przenieś ostatni bit o dwa miejsca w lewo: $(1, 2, 3, \underline{4}, 5, 6)$.

Rosnącą kolejność można uzyskać na inne sposoby za pomocą czterech operacji, ale nie da się tego zrobić w trzech operacjach, więc wynikiem jest $4$.