Cerința

Un șir format din numerele $1,2,\dots ,n$ scrise într-o anumită ordine se numește permutare. Se dă o permutare $p$. Există două tipuri de operații pe care le putem face asupra permutării $p$:

• Stânga: Alegem o valoare $x$ ($1\le x\le n$) și mutăm valoarea $x$ la începutul permutării.
• Dreapta: Alegem o valoare $x$ ($1\le x\le n$) și mutăm valoarea $x$ la finalul permutării.

Tu trebuie să determini numărul minim de operații necesare pentru a ordona crescător elementele permutării $p$.

Date de intrare

Pe prima linie se va afla valoarea $n$ (lungimea permutării). Pe a doua linie se vor afla $n$ valori $p_1,p_2,\dots ,p_n$ (elementele permutării $p$).

Date de ieșire

Pe prima linie se va afișa numărul minim de operații necesare pentru a ordona crescător elementele permutării $p$.

Restricții și precizări

• Pentru toate testele, se respectă $1\le n\le {10}^5$.
• Subtask 1, 40p: $n\le 100$
• Subtask 2, 10p: $n\le 5000$
• Subtask 3, 50p: restricțiile inițiale

Exemplu 1:

Intrare

6
2 1 6 3 5 4

Ieșire

3

Explicație

Numărul minim de operații este $3$:
$2,1,6,3,\underset{―}{5},4\stackrel{dreapta}{\to }2,1,6,3,4,\underset{―}{5}$
$2,\underset{―}{1},6,3,4,5\stackrel{stanga}{\to }\underset{―}{1},2,6,3,4,5$
$1,2,\underset{―}{6},3,4,5\stackrel{dreapta}{\to }1,2,3,4,5,\underset{―}{6}$

Exemplu 2:

Intrare

3
1 2 3

Ieșire

0

Explicație

În acest caz, elementele sunt deja în ordine crescătoare.