#include<bits/stdc++.h> using namespace std; #define d(a)cout<<#a<<" = "<<a<<"\n"; #define f first #define s second #define mp make_pair #define TURBO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long #define MAXN 1000100 ll a[MAXN]; ll pos[MAXN]; int main(){ TURBO; int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; pos[a[i]]=i; } ll wynik=0; ll l=pos[n],r=pos[n]; for(ll s=1;s<=n;s++){ l=min(l,pos[n-s+1]); r=max(r,pos[n-s+1]); if(l<=pos[n-s] and pos[n-s]<=r)continue; ll c=s+s-1-r+l-1; ll a=0,b=0; if(pos[n-s]>r){ a=l-1; b=pos[n-s]-r-1; } else{ a=l-pos[n-s]-1; b=n-r; } wynik+=(max(0LL,min(a,c-b-1)+1)*(b+1)); wynik+=(max(0LL,min(a,c)-max(c-b,0LL)+1)*(c-max(c-b,0LL)+2+c-min(a,c)))/2; //d((max(0LL,min(a,c-b)+1)*(b+1)));d(((min(a,c)-max(c-b,0LL)+1)*(c-max(c-b,0LL)+2+c-min(a,c)))/2);d(s);d(a);d(b);d(c);cout<<"\n"; } cout<<2*n+1<<" "<<wynik; } //5 1 4 3 5 2
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 | #include<bits/stdc++.h> using namespace std; #define d(a)cout<<#a<<" = "<<a<<"\n"; #define f first #define s second #define mp make_pair #define TURBO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long #define MAXN 1000100 ll a[MAXN]; ll pos[MAXN]; int main(){ TURBO; int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; pos[a[i]]=i; } ll wynik=0; ll l=pos[n],r=pos[n]; for(ll s=1;s<=n;s++){ l=min(l,pos[n-s+1]); r=max(r,pos[n-s+1]); if(l<=pos[n-s] and pos[n-s]<=r)continue; ll c=s+s-1-r+l-1; ll a=0,b=0; if(pos[n-s]>r){ a=l-1; b=pos[n-s]-r-1; } else{ a=l-pos[n-s]-1; b=n-r; } wynik+=(max(0LL,min(a,c-b-1)+1)*(b+1)); wynik+=(max(0LL,min(a,c)-max(c-b,0LL)+1)*(c-max(c-b,0LL)+2+c-min(a,c)))/2; //d((max(0LL,min(a,c-b)+1)*(b+1)));d(((min(a,c)-max(c-b,0LL)+1)*(c-max(c-b,0LL)+2+c-min(a,c)))/2);d(s);d(a);d(b);d(c);cout<<"\n"; } cout<<2*n+1<<" "<<wynik; } //5 1 4 3 5 2 |