记录编号	616312	评测结果	AAAAAAAAAA
题目名称	[NOIP 1999]拦截导弹	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2026-06-12 09:27:10	内存使用	3.67 MiB

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;
int b[N];
int a[N];
int t = 1;
int f[N], g[N];

int main(){


	while(cin >> a[t]){
		t ++;
	}
	t --;
	for(int i = 1;i <= t;i ++){
		b[t - i + 1] = a[i];
	}

//	for(int i = 1;i <= t;i ++){
//		cout << a[i] << ' ';
//	}
//	for(int i = 1;i <= t;i ++){
//		cout << b[i] << ' ';
//	}
	int a2 = 1;
	f[1] = a[1];
	for(int i = 2;i <= t;i ++){
		if(a[i] > f[a2]){
			f[++ a2] = a[i];
		}
		else{
			f[lower_bound(f + 1, f + a2 + 1, a[i]) - f] = a[i];
		}
	}
	int a1 = 1;
	g[1] = b[1];
	for(int i = 2;i <= t;i ++){
		if(b[i] >= g[a1]){
			g[++ a1] = b[i];
		}
		else{
			g[upper_bound(g + 1, g + a1 + 1, b[i]) - g] = b[i];
		}
	}
	cout << a1 << '\n';
	cout << a2 << '\n';
	return 0;
}