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
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6 + 9;
int tab[maxn], wyniklewo[maxn];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	for(int i=1; i<=n; i++) {
		cin >> tab[i];
	}	
	deque<int> lewe;
	lewe.push_back(1);
	for(int i=2; i<=n; i++) {
		if(tab[lewe.back()] < tab[i]) {
			lewe.push_back(i);
		}	
	}	
	int wyn = lewe.size(), maxsuf=tab[n];
	for(int i=n; i>1; i--) {
		maxsuf = max(maxsuf, tab[i]);
		while(lewe.size() > 0 && tab[lewe.front()] <= maxsuf) {
			lewe.pop_front();
		}	
		if(lewe.size()>0 && lewe.back() == i) {
			lewe.pop_back();
		}	
		wyniklewo[i] = lewe.size();
		//cout << i << ' ' << lewe.size() << endl;
	}	
	lewe.clear();
	for(int i=n; i>1; i--) {
		if(lewe.size()==0) {
			lewe.push_back(tab[i]);
		}	
		else {
			//cout << " WCHODZi " << i << endl;
			while(lewe.size()>0 && lewe.front() <= tab[i]) {
				lewe.pop_front();
			}	
			lewe.push_front(tab[i]);
			//cout << "WYCHODZI" << endl;
		}	
		wyn=max(wyn, (int)lewe.size() + wyniklewo[i]);
	}	
	cout << wyn;
}