#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
int step1()
{
    vector<int> dp;
    dp.push_back(a[1]);
    for(int i=2;i<=n;i++)
   {
        if(a[i]<=dp.back()){
            	dp.push_back(a[i]);
        }
        else{
            for(int j=0;j<dp.size();j++){
                if(dp[j]<a[i]){
                    dp[j]=a[i];
                    break;
                }
            }
        }
    }
    return dp.size();
}
int step2(){
    vector<int> dp;
    dp.push_back(a[1]);
    for(int i=2;i<=n;i++){
        if(a[i]>dp.back()){
            push_back(a[i]);
        }
        else{
            for(int j=0;j<dp.size();j++){
                if(dp[j]>=a[i]){
                    dp[j]=a[i];
                    break;
                }
            }
        }
    }
    return dp.size();
}
int main(){
    while(scanf("%d",&a[++n])!=EOF);
    n--;
    printf("%d\n",step1());
    printf("%d",step2());
    return 0;
}