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
#include<iostream>
#include<algorithm>

#define rep(a,b) for(int a=0; a<(b); ++a)
#define nl "\n"

using namespace std;

int n, in[1000007], l=0, r=0;

int main()
{
	cin>>n;
	rep(i,n){
		int buf;
		cin>>buf;
		in[buf]=i;
	}
	/*rep(i,n+1){
		clog<<in[i]<<" ";
	}*/
	l=in[n];
	r=in[n];
	clog<<nl;
	long long res=0;
	int med=2*n;
	for(int i=1; i<n+1; ++i){
		//clog<<med<<nl;
		if(med%2){
			l=min(l,in[med/2]);
			r=max(r,in[med/2]);
		}
		else{
			l=min(l,in[med/2]);
			r=max(r,in[med/2+1]);
		}
		int window=i-r+l-1;
		if(window>=0){
			int l_s=max(0,l-window);
			int r_s=min(n-1,r+window);
			//clog<<l_s<<" "<<r_s<<nl;
			res+=r_s-l_s+2-i;
		}
		/*if(window==0){
			clog<<1<<nl;
		}*/
		--med;
	}
	cout<<2*n+1<<" "<<res<<nl;
	//clog<<nl;
	return 0;
}