n∗lognn*lognn∗logn写法，lis[i]的意义为：所有最长上升子序列长度为i的位置上的最小a数组元素值lis[i]的意义为：所有最长上升子序列长度为i的位置上的最小a数组元素值lis[i]的意义为：所有最长上升子序列长度为i的位置上的最小a数组元素值。然后转移一下即可。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}

LL lcm(LL a,LL b){return a/gcd(a,b)*b;}

LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

int n;

const int N=1e5+43;

int dp[N],lis[N],a[N];

int b[N];

int main(){

	ios::sync_with_stdio(false);

	int q;

	while(cin>>q)a[++n]=q;

	// cout<<n<<endl;

	for(int i=1;i<=n;i++)dp[i]=1,lis[i]=2e9,b[n-i+1]=a[i];

	for(int i=1;i<=n;i++){

		int pos=upper_bound(lis+1,lis+1+n,a[i])-lis;

		while(lis[pos]>=a[i])pos--;

		dp[i]=pos+1;

		lis[dp[i]]=min(lis[dp[i]],a[i]);

	}

	int ans1=*max_element(dp+1,dp+1+n);

	for(int i=1;i<=n;i++)a[i]=b[i];

	for(int i=1;i<=n;i++)lis[i]=2e9;

	memset(dp,1,sizeof dp);

	for(int i=1;i<=n;i++){

		int pos=upper_bound(lis+1,lis+1+n,a[i])-lis;

		dp[i]=pos;

		lis[dp[i]]=min(lis[dp[i]],a[i]);

	}

	cout<<*max_element(dp+1,dp+1+n)<<endl;

	cout<<ans1<<endl;

	return 0;

}

// 12

// 6```