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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <vector>
#include <algorithm>
#include <iostream>
#include <stack>

using namespace std;

int main() {
    int n,m,k,a;
    vector<int> v;
    cin>>n;
    for(int i=0; i<n-1; ++i) {
        cin>>a;
        if((v.size() == 0) || (a != v[v.size()-1])) v.push_back(a);
    }
    cin>>a;
    if((v.size() == 0) || ((a != v[v.size()-1]) && (a != v[0]))) v.push_back(a);
    vector<int> w;
    int p,M = 0;
    for(int i=0; i<v.size(); ++i) {
        if(v[i] > M) {
            M = v[i];
            p = i;
        }
    }
    for(int i=p+1; i<v.size(); ++i) w.push_back(v[i]);
    for(int i=0; i<p+1; ++i) w.push_back(v[i]);
    vector<int> V;
    V.push_back(w[w.size()-1]);
    for(int i=0; i<w.size()-1; ++i) {
        if((w[i] < V[V.size()-1]) && (w[i+1] < w[i])) continue;
        V.push_back(w[i]);
    }
    vector<int> W;
    for(int i=1; i<V.size(); ++i) W.push_back(V[i]);
    W.push_back(V[0]);
    stack< pair<int,int> > Stos;
    int q = 0,D = 1;
    while(W[q] < W[q+1]) {
        D++;
        q++;
    }
    Stos.push(make_pair(D,W[q]));
    for(int i=q+1; i<W.size(); ++i) {
        pair<int,int> S;
        S = Stos.top();
        int d = 1;
        while((W[i] < W[i+1]) && (i+1 < W.size())) {
            while((!Stos.empty()) && (W[i+1] >= S.second)) {
                if(W[i+1] > S.second) d = max(d,S.first);
                else d = max(d+1,S.first)-1;
                Stos.pop();
                if(!Stos.empty()) S = Stos.top();
            }
            d++;
            i++;
        }
        Stos.push(make_pair(d,W[i]));
    }
    pair<int,int> ans;
    ans = Stos.top();
    cout<<ans.first<<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}