#include<iostream>

 #include<cstdio>

 #include<algorithm> 

 using namespace std;

 int n,a[],f[],dp[],len = ,tot = ,p;

 int main() {

     while(scanf("%d",&a[++p]) != EOF);

     f[] = a[];

     dp[] = a[];

     p--;

     for(int i = ;i <= p; i++) {

         if(a[i] <= f[len])

             f[++len] = a[i];

         else {

             int u = upper_bound(f+,f+len+,a[i],greater<int>()) - f;

             f[u] = a[i];

         }

         if(a[i] > dp[tot])

             dp[++tot] = a[i];

         else {

             int o = lower_bound(dp+,dp+tot+,a[i]) - dp;

             dp[o] = a[i];

         }

     }

     printf("%d\n%d",len,tot);

     return ;

 }