# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
62057917 |
Practice:
wyxdrqc |
5E
- 9
|
C++14 (GCC 6-32)
|
Accepted
|
560 ms
|
29688 KB
|
2019-10-07 15:42:32 |
2019-10-07 15:42:32 |
|
#include<cstdio>
#include<iostream>
#include<cctype>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 1e6 + 3;
int a[N],pre[N],suf[N];
int n;
int s[N],top;
LL g[N];
vector <int> G;
int main(){
int pos = 0,maxx = 0;
scanf("%d",&n);
for(int i = 1;i <= n;++i){
scanf("%d",&a[i]);
if(a[i] > maxx) maxx = a[i],pos = i;
}
for(int i = pos + 1;i <= n;++i) G.push_back(a[i]);
for(int i = 1;i < pos;++i) G.push_back(a[i]);
LL ans = 0;
for(int i = 0;i < (int)G.size();++i) pre[i + 1] = max(pre[i],G[i]);
for(int i = G.size() - 1;i >= 0;--i) suf[i + 1] = max(suf[i + 2],G[i]);
for(int i = 1;i < n;++i) if(pre[i] == G[i - 1] || suf[i] == G[i - 1]) ans++;
for(int i = 0;i < (int)G.size();++i){
int cnt = 0;
while(top && G[s[top]] <= G[i]){
if(G[s[top]] == G[i]) cnt += g[top];
top--;
}
ans += cnt;
if(top) ans ++;
s[++top] = i;
g[top] = cnt + 1;
}
top = 0;
for(int i = G.size() - 1;i >= 0;--i){
while(top && G[s[top]] <= G[i]) top--;
if(top) ans++;
s[++top] = i;
}
printf("%lld\n",ans);
return 0;
}
/*
10
2 2 2 1 1 2 2 2 1 2
*/
Click to see test details