#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],seg[(SS<<1)+10],sp[N],ile[N],n;
pair<int,int> sorted[N];
vi g[N];
void upd(int a,int b){
for(a+=SS;a>0;a>>=1) seg[a]+=b;
}
int Query(int a,int b){
int res=0;
for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
if(!(a&1)) res+=seg[a+1];
if(b&1) res+=seg[b-1];
}
return res;
}
void clear(int v){
if(v>(SS<<1) or seg[v]==0) return;
seg[v]=0;
clear(v<<1),clear((v<<1)+1);
}
ll big(int x){
int mini=INT_MAX;
sp[0]=0;
for(int i=1;i<=n;i++) sp[i]=sp[i-1]+(t[i]==x?1:-1),mini=min(mini,sp[i]);
if(mini<0){
for(int i=0;i<=n;i++) sp[i]+=abs(mini);
}
upd(sp[0],1);
ll res=0;
for(int i=1;i<=n;i++){
res+=(ll)Query(0,sp[i]-1);
upd(sp[i],1);
}
clear(1);
return res;
}
ll sum(ll a,ll b){
return a*b-((b*(ll)(b-1))>>1LL);
}
ll small(int x){
ll res=0;
for(int i1=0;i1<g[x].size();i1++){
for(int i2=i1;i2<g[x].size();i2++){
int p=(i1==0?1:g[x][i1-1]+1),k=(i2==g[x].size()-1?n:g[x][i2+1]-1),ile=i2-i1+1;
int dl=(ile<<1)-1;
int pocz=max(p,k-dl+1),prz=max(p,g[x][i2]-dl+1);
if(prz>g[x][i1]) continue;
if(pocz>g[x][i1]) res+=sum(g[x][i1]+dl-g[x][i2],g[x][i1]-prz+1);
else{
res+=(ll)(g[x][i1]-pocz)*(ll)(k-g[x][i2]+1);
res+=sum(k-g[x][i2]+1,pocz-prz+1);
}
}
}
return res;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>sorted[i].fi;
sorted[i].se=i;
}
sort(sorted+1,sorted+1+n);
int curr=0;
for(int i=1;i<=n;i++){
if(i==1 or sorted[i].fi!=sorted[i-1].fi) curr++;
t[sorted[i].se]=curr;
}
for(int i=1;i<=n;i++) ile[t[i]]++;
for(int i=1;i<=n;i++) g[t[i]].push_back(i);
int p=sqrt(n)<<1;
ll res=0;
for(int i=1;i<=curr;i++){
if(ile[i]>p) res+=big(i);
else res+=small(i);
}
cout<<res<<"\n";
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
int tt=1;
while(tt--) solve();
}
Compilation message
Main.cpp: In function 'll small(int)':
Main.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i1=0;i1<g[x].size();i1++){
| ~~^~~~~~~~~~~~
Main.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i2=i1;i2<g[x].size();i2++){
| ~~^~~~~~~~~~~~
Main.cpp:62:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | int p=(i1==0?1:g[x][i1-1]+1),k=(i2==g[x].size()-1?n:g[x][i2+1]-1),ile=i2-i1+1;
| ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:89:18: error: invalid operands of types '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} and 'int' to binary 'operator<<'
89 | int p=sqrt(n)<<1;
| ~~~~~~~^~~
| | |
| | int
| __gnu_cxx::__enable_if<true, double>::__type {aka double}
