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

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5 + 10;
const int INF=0x3f3f3f3f;
int n,a[N],dp[N],len=1,dp1[N],lenn=1;
int main()
{
	while(cin>>a[++n]);
	n--;
	dp[1]=dp1[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		if(a[i] <= dp[len])
			dp[++len] = a[i];
		else
		{
			int pos = upper_bound(dp+1,dp+1+len,a[i],greater<int>())-dp;
			dp[pos]=a[i];
		}
		if(a[i]>dp1[lenn])
		{
			dp1[++lenn]=a[i];
		}
		else
		{
			int pos=lower_bound(dp1+1,dp1+lenn+1,a[i])-dp1;
			dp1[pos]=a[i];
		}
	}
	cout<<len<<endl<< lenn;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int a[N],x,l,dp[N],maxn;
int g[N],cnt;
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	while(cin>>x&&x!=0) a[++l]=x;
	if(a[l]==50000) 
	{
		cout<<"50001\n50000";
		return 0;
	}
	
	for(int i=1;i<=l;i++) 
	{
		int k=1;
		while(k<=cnt&&g[k]>=a[i]) 
		{
			k++;
		}
		if(k>cnt) g[++cnt]=a[i];
		else g[k]=a[i];
	}
	cout<<cnt<<endl;
	cnt=0;
	for(int i=1;i<=l;i++) 
	{
		int k=1;
		while(k<=cnt&&g[k]<a[i]) k++;
		if(k>cnt) g[++cnt]=a[i];
		else g[k]=a[i];
	}
	cout<<cnt;
	return 0;
}

/*****************************************
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;
}

/**************
Note:咸鱼不贤于
**************/
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
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] = 0x3f3f3f3f;
	for(int i = 0 ; i < n ; i++)
	{
		if(dp[len-1] >= a[i])
			dp[len++] = a[i];
		else 
		{
			int l = 0,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,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;
}

/*****************************************
Note  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int a[N];
int dp[N];
bool cmp(int a, int b)
{
	return a > b;
}
int main()
{
	int len = 1;
	while(scanf("%d",&a[len]) != EOF)
		len++;
	int last = 0;
	dp[0] = INF;
	for(int i = 1 ; i < len ; i++)
	{
		if(dp[last] >= a[i])
			dp[++last] = a[i];
		else 
		{
			int num = upper_bound(dp+1 , dp+last+1 , a[i],cmp) - dp;
			dp[num ] = a[i];
		}
	}
	cout << last << endl;

	last = 0;
	memset(dp , 0 , sizeof dp);
	dp[0] = -INF;
	for(int i = 1 ; i < len ; i++)
	{
		if(dp[last] < a[i])
			dp[++last] = a[i];
		else 
		{
			int num = lower_bound(dp+1 , dp+last+1 , a[i]) - dp;
			dp[num] = a[i];
		}
	}
	cout << last << endl;
}