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
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int ile;
cin>>ile;
vector<int> pary(2*ile);
for(int i=0;i<ile;i++) cin>>pary[i];
for(int i=0;i<ile;i++) pary[i+ile]=pary[i];
int roz=2*ile;
vector<int> gora(roz,-1);
vector<int> stos;
for(int i=0;i<roz;i++){
		while(!stos.empty() && pary[i]>pary[stos.back()]){
			gora[stos.back()]=i;
			stos.pop_back();
		}
		stos.push_back(i);
}
int pom=21;
vector<vector<int>> dol(pom,vector<int>(roz,-1));
for(int i=0;i<roz;i++) dol[0][i]=gora[i];
for(int j=1;j<pom;j++){
		for(int i=0;i<roz;i++){
			int pos=dol[j-1][i];
			dol[j][i]= (pos==-1? -1 : dol[j-1][pos]);
		}
}
int wyn=0;
for(int i=0;i<ile;i++){
	int licz=i;
	int suma=0;
	for(int j=pom-1;j>=0;j--)
{
			int czy=dol[j][licz];
			if(czy!=-1 && czy<i+ile){
				suma += (1<<j);
				licz = czy;
			}
	}
	wyn = max(wyn,suma+1);
}
cout<<wyn<<"\n";
return 0;
}