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
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, mx=0, i;
    cin >> n;
    vector<int> nums(n);
    for(i=0; i<n; ++i){
        cin >> nums[i];
        if(nums[i]>=nums[mx]) mx=i;
    }
    vector<int> new_nums(n);
    for(i=0; i<n; ++i) new_nums[(i+(n-1-mx))%n] = nums[i];
    nums = new_nums;
    
    vector<int> dp(n, 1);
    vector<int> next_greater(n, -1);
    stack<int> curr;
    for(i=n-1; i>=0; i--){
        while(!curr.empty() && nums[curr.top()]<=nums[i]) curr.pop();
        if(!curr.empty()) next_greater[i] = curr.top();
        curr.push(i);
    }
    int output = 1;
    for(i=n-1; i>=0; i--){
        if(nums[i]==nums[n-1]) continue;
        dp[i] = 1+dp[next_greater[i]];
        output = max(output, dp[i]);
    }
    cout << output;
}