using namespace std;
int a[(int)1e5+1];
int s[(int)1e5+1];
int find(int x,int l,int r)
{
	int mid=(l+r)/2;
	if(l==r)return mid;
	if(s[mid]<=x)return find(x,l,mid);
	return find(x,mid+1,r);
}
int find2(int x,int l,int r)
{
	int mid=(l+r)/2;
	if(l==r)return mid;
	if(s[mid]>x)return find(x,l,mid);
	return find(x,mid+1,r);
}
int main()
{
	string t;
	getline(cin,t);
	int n=1,t2;
	for(int i=0;i<t.size();i++)
	{
		if(t[i]==' ')
		{
			n++;
			continue;
		}
		a[n]=a[n]*10+t[i]-'0'; 
	}
	t2=0;
	s[0]=50001;
	for(int i=1;i<=n;i++)
	{
		if(s[t2]>=a[i])
		{
			s[++t2]=a[i];
		}
		s[find(a[i],1,t2)]=a[i];
	}
	printf("%d\n",t2);
	s[0]=-1;
	t2=0;
	for(int i=1;i<=n;i++)
	{
		if(s[t2]<a[i])
		{
			s[++t2]=a[i];
		}
		s[find2(a[i],1,t2)]=a[i];
	}
	printf("%d",t2);
	return 0;
}