F - The Monochrome Picture

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cmath>
#include <limits>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <set>
#include <ctime>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define inf 2147483647
#define eps 0.0000000001
#define e  2.718281828459
#define mod 1000000007
#define LL long long
#define ULL unsigned long long
const double pi = acos(0.0)*2.0;

//  memset(array, value, sizeof(array));
//  cout<<fixed<<setprecision(3)<<"\nExecution time="<<clock()/1000.0<<endl;
//  freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);


set <pair<int, int> > st;
int lng[1000100], ind[1000100], prv[100100], ans[100100], A[100100];

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int i, j, k, n, m;
    for(i = 0; i <= 1000001; i++)
    {
        lng[i] = -10000;
        ind[i] = -10000;
    }
    lng[i] = 0;
    ind[i] = -1;
    st.insert({ 0, 1000002 });
    scanf(" %d", &n);
    int best = 0, bestind = -1;
    for(i = 0; i < n; i++)
    {
        scanf(" %d", A + i);

        auto it1 = st.find({ lng[A[i] + 1], A[i] + 1 });
        if(it1 != st.end())
            st.erase(it1);

        auto it2 = st.find({ lng[A[i] - 1], A[i] - 1 });
        if(it2 != st.end())
            st.erase(it2);

        auto cur = *(st.rbegin());
        prv[i] = ind[cur.second];
        ans[i] = cur.first + 1;
        if(ans[i]>best)
        {
            best = ans[i];
            bestind = i;
        }

        auto it3 = st.find({ lng[A[i]], A[i] });
        if(it3 != st.end())
            st.erase(it3);

        ind[A[i]] = i;
        lng[A[i]] = ans[i];

        if(lng[A[i] - 1] >= 0)
            st.insert({ lng[A[i] - 1], A[i] - 1 });
        if(lng[A[i] + 1] >= 0)
            st.insert({ lng[A[i] + 1], A[i] + 1 });
        st.insert({ lng[A[i]], A[i] });
    }
    printf("%d\n", n - best);
    stack <int> stk;
    while(bestind >= 0)
    {
        stk.push(A[bestind]);
        bestind = prv[bestind];
    }
    printf("%d", stk.top());
    stk.pop();
    while(!stk.empty())
    {
        printf(" %d", stk.top());
        stk.pop();
    }
    printf("\n");
}