下面是代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int tree[N << 1], a[N], n, mx, ans, ans2;
//id代表线段树的节点，l和r分别代表此节点的左端点和右端点，x代表更改节点，y代表更改数值
void update(int id, int l, int r, int x, int y) {
	if(l == r) {
		tree[id] = tree[id] > y ? tree[id] : y;
		return;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) update(id << 1, l, mid, x, y);
	else update(id << 1 | 1, mid + 1, r, x, y);
	tree[id] = tree[id << 1] > tree[id << 1 | 1] ? tree[id << 1] : tree[id << 1 | 1];
}
//id, l, r含义同update， x和y分别代表查询的左端点和右端点
int query(int id, int l, int r, int x, int y) {
	if(x <= l && r <= y) return tree[id];
	int mid = (l + r) >> 1, ans = 0;
	if(x <= mid) ans = query(id << 1, l, mid, x, y);
	if(y > mid) ans = max(ans, query(id << 1 | 1, mid + 1, r, x, y));
	return ans;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	while(cin >> a[++n])mx = mx > a[n] ? mx : a[n]; --n;
	for(int i = 1; i <= n; ++i) {
		int aa = query(1, 1, mx, a[i], mx);
		update(1, 1, mx, a[i], aa + 1);
		ans = ans > aa + 1 ? ans : aa + 1;
	}
	cout << ans << endl;
	memset(tree, 0, sizeof(tree));
	for(int i = 1; i <= n; ++i) {
		int aa = query(1, 1, mx, 1, a[i] - 1);
		update(1, 1, mx, a[i], aa + 1);
		ans2 = ans2 > aa + 1 ? ans2 : aa + 1;
	}
	cout << ans2;
	return 0;
}