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
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

long ai[1000002];
long ia[1000002];

int main(){
	long n;
	long long cel;
	cin >>n;
	cel =2*n+1;
	for(long i=1;i<=n;i++) {
		cin>>ai[i];
		ia[ai[i]]=i;
	//	cout<<i<< " "<<ai[i]<<endl;
	}
	long long Y=0,medianacal,left=0,right=0,temp=0,diff=0,nadmiar=0,mozliwosci=0,p0=0,p1=0;

	Y=cel-n;
	medianacal=Y/2;
	left=right= ia[n];

	for(long y=n-1;y>=medianacal;y--) {
		temp = ia[y];

		if(temp<left) left =temp;
		else if(temp>right) right = temp;
	}
	for(long long x=n;x>=1;x--) {
		Y=cel-x;
		medianacal=floor(Y/2);
	//	cout <<" mediana " << medianacal<<endl;
		while(ai[left]<medianacal) {if(left==right) break;left++;}
		while(ai[right]<medianacal) {if(left==right) break;right--;}

		diff=right-left;
		nadmiar= x-diff;
		
		p0=max((long long)0,right-x);
		p1=min(n-x,left-1);
		if(nadmiar>=0) {
			mozliwosci+=p1-p0+1;
		}
	//	cout << "diff" <<diff << " nadmiar" << nadmiar << " moz"<<mozliwosci<< " x "<<x <<" L" << left <<" R" <<right <<endl;
	//	cout <<" p0=" <<p0 << " p1=" << p1 << " p1-p0+1="<<p1-p0+1<<endl;
		

		
		
	}
	
	cout <<cel << " " <<mozliwosci<<endl;
    return 0;
}