#include <fstream>
#include <iostream>
#define nmax 5001
#define f for
#define w while

using namespace std;

ifstream fin("decrease.in");
ofstream fout("decrease.out");

int n,a[nmax],b[nmax],poz[nmax],i,m,nr=1;

inline void read()
{
    fin>>n;
    f(i=1; i<=n; i++)
    fin>>a[i];
    fin.close();
}

int cauta(int p,int u,int x)
{
    int m;
    w(p<=u)
    {
        m=p+(u-p)/2;
        if(x<a[b[m]])
            p=m+1;
        else
            u=m-1;
    }
    return p;
}

inline void write()
{
    fout<<m<<' '<<nr<<'\n';
    f(i=b[m]; i>0; i=poz[i])
    fout<<a[i]<<' ';
    fout.close();
}

inline void solve()
{
    int k;
    a[0]=-1999999999;
    f(i=1; i<=n; i++)
    {
        poz[i]=0;
        k=cauta(1,m,a[i]);
       // if(k==m)nr++;
        if(k>m)
        {
            poz[i]=b[k-1];
            m=k;
            b[k]=i;
            //nr=1;
        }
        else
        {
            poz[i]=b[k-1];
            if(a[b[k]]<a[i])
                {
                    b[k]=i;
                    nr++;
                }
        }
    }
}


int main()
{
    read();
    solve();
    write();
    return 0;
}