#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std ;

const int INF=0xfffffff ;

struct node

{

    int s,t,cap,nxt ;

}e[] ;

int m,n,cnt,head[],level[],q[] ;

void add(int s,int t,int cap)

{

    e[cnt].s=s ;e[cnt].t=t ;e[cnt].cap=cap ;e[cnt].nxt=head[s] ;head[s]=cnt++ ;

    e[cnt].s=t ;e[cnt].t=s ;e[cnt].cap= ;e[cnt].nxt=head[t] ;head[t]=cnt++ ;

}

bool build(int s,int t)

{

    int front=,rear= ;

    memset(level,-,sizeof(level)) ;

    q[rear++]=s ;

    level[s]= ;

    while(front<rear)

    {

        int u=q[front++] ;

        for(int i=head[u] ;i!=- ;i=e[i].nxt)

        {

            int tt=e[i].t ;

            if(level[tt]==- && e[i].cap>)

            {

                level[tt]=level[u]+ ;

                if(tt==t)return true ;

                q[rear++]=tt ;

            }

        }

    }

    return false ;

}

int find(int s,int t,int flow)

{

    if(s==t)return flow ;

    int ret=,a ;

    for(int i=head[s] ;i!=- ;i=e[i].nxt)

    {

        int tt=e[i].t ;

        if(level[tt]==level[s]+ && e[i].cap>)

        {

            a=find(tt,t,min(e[i].cap,flow-ret)) ;

            e[i].cap-=a ;

            e[i^].cap+=a ;

            ret+=a ;

            if(ret==flow)

                return ret ;

        }

    }

    if(!ret)level[s]=- ;

    return ret ;

}

int dinic(int s,int t)

{

    int flow,ret= ;

    while(build(s,t))

        while(flow=find(s,t,INF))

            ret+=flow ;

    return ret ;

}

int a[],dp[] ;

int main()

{

    while(~scanf("%d",&n))

    {

        for(int i= ;i<=n ;i++)

            scanf("%d",&a[i]) ;

        int ans= ;

        for(int i= ;i<=n ;i++)

        {

            dp[i]= ;

            for(int j= ;j<i ;j++)

                if(a[j]<a[i] && dp[j]+>dp[i])

                    dp[i]=dp[j]+ ;

            ans=max(ans,dp[i]) ;

        }

        int S,T ;

        S= ;T=*n+ ;

        cnt= ;

        memset(head,-,sizeof(head)) ;

        for(int i= ;i<=n ;i++)

        {

            add(i,i+n,) ;

            if(dp[i]==)add(S,i,) ;

            if(dp[i]==ans)add(i+n,T,) ;

            for(int j=i+ ;j<=n ;j++)

            {

                if(dp[j]==dp[i]+)

                    add(i+n,j,) ;

            }

        }

        printf("%d\n%d\n",ans,dinic(S,T)) ;

    }

    return  ;

}