Un numar natural se numeste “numar scara” daca toate cifrele lui sunt ordonate crescator, de la stanga la dreapta. De exemplu 11223569 este un “numar scara”, dar 98873 si 122429 nu sunt.

Cerința

Mihnea primeste o radiera si o foaie pe care este scris un sir de cifre nenule. El trebuie sa stearga cat mai putine cifre cu proprietatea ca daca lipim cifrele ramase in ordinea din sir vom avea un “numar scara”. De exemplu daca avem sirul 2 1 1 3 4 8 5 , stergem cifra de pe pozitia 1 si cea de pe pozitia 6, lipim cifrele ramase si ne rezulta numarul 11345 care este un “numar scara” , deci numarul minim de stergeri este 2.

Date de intrare

Fișierul de intrare radiera.in conține pe prima linie numărul N, iar pe a doua linie n numere naturale separate prin spații, reprezentand sirul.

Date de ieșire

Fișierul de ieșire radiera.out va conține pe prima linie numarul minim de stergeri care trebuie sa le faca Mihnea.

Restricții și precizări

• 3 ≤ N ≤ 1000

Exemplu

radiera.in

7
2 1 1 3 4 8 5

radiera.out

2

Explicație

Mihnea sterge cifra 2 si cifra 8.

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

ifstream cin("radiera.in");
ofstream cout("radiera.out");

int n , a[1002] , L[1002] , P[1002] , l , lmax;

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];
    for(int i = n ; i >= 1 ; i--)
    {
        l = 0;
        for(int j = i + 1 ; j <= n ; j++)
            if(a[i] <= a[j] && L[j] > l) l = L[j];
        L[i] = l + 1;
        if(L[i] > lmax) lmax = L[i];
    }
    cout << n - lmax;
    return 0;
}