/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int a[N];
int dp[N];
int main()
{
    int n = 0;
    while(cin >> a[n])
        n++;
    int len = 1;
    dp[0] = INF;
    for(int i = 0 ; i < n ; i++)
    {
        if(dp[len - 1] >= a[i])
            dp[len++] = a[i];
        else
        {
            int l = 0;
            int r = len - 1;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(dp[mid] >= a[i])
                    l = mid + 1;
                else
                    r = mid;
            }
            dp[l] = a[i];
        }
    }
    cout << len - 1 << endl;
    memset(dp,-1,sizeof(dp));
    len = 1;
    for(int i = 0 ; i < n ; i++)
    {
        if(dp[len - 1] < a[i])
            dp[len++] = a[i];
        else
        {
            int l = 0;
            int r = len - 1;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(dp[mid] >= a[i])
                    r = mid;
                else
                    l = mid + 1;
            }
            if(l != 0)
                dp[l] = a[i];
        }
    }
    cout<< len - 1 <<endl;
    return 0;
}