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,\underline{5},4 \xrightarrow{dreapta} 2,1,6,3,4,\underline{5}\)
\(2,\underline{1},6,3,4,5 \xrightarrow{stanga} \underline{1},2,6,3,4,5\)
\(1,2,\underline{6},3,4,5 \xrightarrow{dreapta} 1,2,3,4,5,\underline{6}\)

Exemplu 2:

Intrare

3
1 2 3

Ieșire

0

Explicație

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