CFR 606 C. Sorting Railway Cars ( Ad hoc )

http://codeforces.com/contest/606/problem/C
Imagine if we decided exactly which cars are going to be moved, and of course each of them will be moved no more than once( quite obvious ). The ones left, putting them into a separate sequence, we will find that they will be all consecutive values. So that will mean the maximum number of cars we don't need to move, is exactly the length of the longest subrange in A, such that it is of an arithmetic progression with common difference = 1.

void solve(){
    int N; cin >> N;
    vi A( N + 1 );
    for( int i = 1; i <= N; ++i )
        cin >> A[ i ];
    vi pos( N + 1 );
    for( int i = 1; i <= N; ++i )
        pos[ A[ i ] ] = i;
    int ans = 1;
    for( int i = 2, cnt = 1; i <= N; ++i ){
        if( pos[ i ] < pos[ i - 1 ] )
            cnt = 1;
        else
            ++cnt;
        ans = max( ans, cnt );
    }
    cout << N - ans << "\n";
}