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
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
long long n,t[1000005],tab[1000005],mi,ma,q,p,k,z,x;
int main(){
  scanf("%lld",&n);
  for(int i=1;i<=n;i++){
    scanf("%lld",&t[i]);
    tab[t[i]]=i;
  }
  mi=tab[n],ma=tab[n];
  for(int i=n;i>=1;i--){
    if((n-i)%2==1){
      q=(n+i-1)/2;
      mi=min(mi,tab[q]),ma=max(ma,tab[q]);
    }
    z=n-i+1;
    p=ma-z+1,k=n-z+1;
    p=max(p,1LL),k=min(k,mi);
    //cout<<mi<<" "<<ma<<" "<<z<<"  "<<k-p+1<<"\n";
    if(k>=p) x+=k-p+1;
  }
  printf("%lld %lld",2*n+1,x);
  return 0;
}