nlogn lis

///:-)
#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define inf 2000000000
#define infLL 9000000000000000000
#define infULL 18446744073709551615
#define Aktaruzzaman using
#define pi (2.0*acos(0.0))
#define Pramanik namespace std;
#define vsort(v)   sort(v.begin(),v.end())
#define ull unsigned long long int
#define mem(a, b) memset(a, b, sizeof a)
#define cf 1000002
#define MOD 1000000007
#define pii pair<int, int>

//int dx[]={0,1,0,-1};
//int dy[]={1,0,-1,0};
//int dx[]={1,1,0,-1,-1,-1,0,1};
//int dy[]={0,1,1,1,0,-1,-1,-1};

template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template< class T > inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/gcd(a,b))*b;}
template <class T> inline T is_prime(T a){if(a<2|a==4)return false;if(a==2||a==3||a==5)return true; T g=(T)sqrt(a)+1; for(T i=2; i<=g; i++){if(a%i==0)return false;}return false;}
template <class T> inline T bigmod(T n,T p,T m){if(p==0)return 1; if(p%2)return ((n%m)*bigmod(n,p-1,m))%m; else {T c=bigmod(n,p/2,m);return ((c%m)*(c%m))%m;}}

Aktaruzzaman Pramanik

int a[cf], tailInd[cf], prev[cf];
int n;
stack<int>st;
int bs(int st, int en, int val)
{
    int lo=st, hi = en, p;

    while(lo<=hi){
        int mid = (lo+hi)/2;

        if(a[tailInd[mid]]>=val){
            p = mid;
            hi=mid-1;
        }
        else lo=mid+1;

    }
    return p;
}

int getLis()
{
    int len = 1;
    int i;
    for(i=1; i<n; i++){

        if(a[i]<a[tailInd[0]]){
            tailInd[0]=i;
        }

        else if(a[i]>a[tailInd[len-1]]){
            prev[i] = tailInd[len-1];
            tailInd[len++]=i;
        }

        else{

            int pos = bs(0, len-1, a[i]);

            prev[i] = tailInd[pos-1];
            tailInd[pos]=i;

        }

    }

     i = tailInd[len-1];

     while(1){
        st.push(a[i]);
        if(prev[i]<0)break;
        i=prev[i];
     }

    return len;

}

int main()

{
  /*ios_base:: sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);*/

    int i, j, k;

    scanf("%d", &n);

    for(i=0; i<n; i++)scanf("%d", &a[i]);
    mem(tailInd, 0);
    mem(prev, -1);


    int len = getLis();

    cout<<"Size : "<<len<<endl;

    while(!st.empty()){
        cout<<st.top()<<" ";
        st.pop();
    }
    cout<<endl;

}