1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6+7;
int t[MAXN];
int part[MAXN];
int mx[MAXN];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	
	for (int i=0; i<n; i++) cin >> t[i];
	
	for (int i=n-1; i>=0; i--) mx[i] = max(mx[i+1],t[i]);
	
	stack<int> st;
	
	for (int i=n-1; i>=0; i--) {
		while (!st.empty() && st.top() <= t[i]) st.pop();
		st.push(t[i]);
		part[i] = st.size();
	}
	
	int res = part[0];
	vector<int> v;
	for (int i=0; i<n-1; i++) {
		if (v.empty() || v.back() < t[i]) v.push_back(t[i]);
		auto lb = lower_bound(v.begin(), v.end(), mx[i+1]);
		while (lb != v.end() && *lb <= mx[i+1]) lb++;
		int r = v.size()-(lb-v.begin());
		res = max(res, part[i+1] + r);
		//cout << part[i+1] << "," << r << "\n";
	}
	
	cout << res << "\n";
}