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.

#include <bits/stdc++.h>
using namespace std;

int n , x , l , A[100001] , p;

int cautare_binara(int x , int n)
{
    int st = 1 , dr = n;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(A[mij] > x) dr = mij - 1;
        else st = mij + 1;
    }
    return st;
}
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        p = cautare_binara(x , l);
        if(A[p] <= x) l++ , p = l;
        A[p] = x;
    }
    cout << n - l;
}