考场上读错题，直接炸裂。
题目中说“任一”的意思是优弧与劣弧中随便一个满足条件即可，不是要求都满足要求。
很明显可以用单调栈。
常规做法是将环拆开，变成\(2n\)的链，然后直接跑单调栈，会\(T\)。
题解的做法是将某个最大值放在端点，因为很明显如果你的某个弧上有最大值，那他一定不合法，而将最大值放在一个端点可以避免考虑这种不合法的弧从而减少枚举，降低复杂度。
最后要注意的是原来是个环，大于或等于\(a[n]\)的一些值也许可以和最大值配对，这些答案要考虑。
Code
#include<bits/stdc++.h>
using namespace std;
namespace STD
{
#define rr register
typedef long long ll;
const int inf=INT_MAX;
const int N=5e6+4;
int n;
int a_[N];
struct pack
{int val,num;}a[N];
int read()
{
rr int x_read=0,y_read=1;
rr char c_read=getchar();
while(c_read<'0'||c_read>'9')
{
if(c_read=='-') y_read=-1;
c_read=getchar();
}
while(c_read<='9'&&c_read>='0')
{
x_read=(x_read<<3)+(x_read<<1)+(c_read^48);
c_read=getchar();
}
return x_read*y_read;
}
class Stack
{
public:
pack *Top;
pack s[N];
Stack(){Top=s;}
inline pack top(){return *Top;}
inline void push(pack x){*(++Top)=x;}
inline void pop(){Top--;}
inline bool empty(){return Top==s;}
inline size_t size(){return Top-s;}
}s;
};
using namespace STD;
int main()
{
n=read();
int maxn=-inf,id;
for(int i=1;i<=n;i++)
{
a_[i]=read();
if(a_[i]>maxn)
{
maxn=a_[i];
id=i;
}
}
int po=1;
for(int i=id;i<=n;i++)
a[po].val=a_[i],a[po++].num=0;
for(int i=1;i<id;i++)
a[po].val=a_[i],a[po++].num=0;
po--;
ll ans=0;
for(int i=1;i<=n;i++)
{
if(s.empty()){a[i].num=1;s.push(a[i]);continue;}
if(a[i].val==s.top().val)
{
a[i].num=s.top().num+1;
ans+=s.top().num;
if(s.size()>s.top().num)
ans++;
s.push(a[i]);
continue;
}
if(a[i].val<s.top().val)
{
a[i].num=1;
ans++;
s.push(a[i]);
continue;
}
while(!s.empty()&&s.top().val<a[i].val)
{
ans++;
s.pop();
}
if(s.empty()){a[i].num=1;s.push(a[i]);continue;}
if(a[i].val==s.top().val)
{
a[i].num=s.top().num+1;
ans+=s.top().num;
if(s.size()>s.top().num)
ans++;
s.push(a[i]);
continue;
}
ans++;
a[i].num=1;
s.push(a[i]);
}
pack *p=s.s+1;
int cnt=0;
while(cnt<3&&p<s.Top)
{
if(p->val!=(p-1)->val)
cnt++;
if(cnt==3) break;
p++;
}
if(cnt==3)
{
while(s.Top>=p)
{
s.pop();
ans++;
}
}
else
{
if(cnt>1)
while(s.top().val==a[n].val)
s.pop(),ans++;
}
cout<<ans<<'\n';
}