Rezolvare PBinfo #2242

Se consideră un șir a[1], a[2], …, a[n] de numere distincte din mulțimea {1, 2, ..., n}. O operație constă din extragerea unui număr din șir de la o anumită poziție și inserarea lui în altă poziție a șirului. De exemplu, dacă a = 1, 2, 5, 3, 6, 4, atunci 5 poate fi inserat după 3 și se obține a = 1, 2, 3, 5, 6, 4.

Cerința

Să se obțină șirul ordonat crescător efectuând un număr minim de operații de inserare.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran un singur număr natural reprezentând numărul minim de operații de inserare necesar ordonării crescătoare a șirului.

Restricții și precizări

• 1 ≤ n ≤ 100 000

Exemplu:

Intrare

6
1 2 5 3 6 4

Ieșire

2

Explicație

O soluție de ordonare efectuând două operații este următoarea. Se ia 5 și se inserează după 3. Se obține 1, 2, 3, 5, 6, 4. Se ia apoi 4 și se inserează după 3. Se obține 1, 2, 3, 4, 5, 6.