#include <cstdio>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <unordered_map>
#include <cmath>
#include <memory.h>
#include <cstring>
#include <climits>
#define map unordered_map
using namespace std;
#define prc(x) printf(#x":%c\n",x)
#define pri(x) printf(#x":%d\n",x)
#define prl(x) printf(#x":%lld\n",x)
#define ll long long
#define ull unsigned long long
using namespace std;
int h[100005],n=1;
int f[100005];
// f[i] 表示长度为 i 的不升子序列的结尾最大值
int solve1(){
f[0]=INT_MAX;
int maxlen=0;
for(int i=1;i<=n;i++){
int l=0,r=maxlen,ans=0;
while(l<=r){
// printf("%d %d\n",l,r);
int mid=l+r>>1;
if(f[mid]>=h[i]){
l=mid+1,ans=mid;
}else r=mid-1;
}
ans++;
// printf("%d %d\n",ans,maxlen);
maxlen=max(maxlen,ans);
f[ans]=h[i];
}
return maxlen;
}
// f[i] 表示第 i 个系统的最低高度
int solve2(){
memset(f,0x3f,sizeof(f));
int maxlen=0;
f[0]=0;
for(int i=1;i<=n;i++){
int l=0,r=maxlen+1,ans=1;
while(l<=r){
int mid=l+r>>1;
if(f[mid]<h[i]) l=mid+1,ans=mid;
else r=mid-1;
}
// printf("%d\n",ans);
ans++;
maxlen=max(maxlen,ans);
f[ans]=h[i];
}
}
int main(){
while(scanf("%d",h+n)==1)n++;
n-=1;
// printf("%d\n",n);
printf("%d\n",solve1());
printf("%d\n",solve2());
}
