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
#include<bits/stdc++.h>

using namespace std;

int A[(int)1e6+6];

int R[(int)2e6+6];
int L[(int)2e6+6];


int main(){
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
	int n;cin>>n;
	for(int i=0;i<n;i++)cin>>A[i];
	
	
	int l=0;int r=n-1;
	for(int k=n+1;k<2*n;k++){
		R[k]=R[k-1];L[k]=L[k-1];
		int o=l;int f=r;
		while(2*A[l]<k)l++;
		while(2*A[r]<k)r--;
		
		R[k]+=f-r;L[k]+=l-o;
		//cout<<k<<" "<<B[k]<<"\n";
	}
	long long X=1;
	for(int i=1;i<n;i++){
		if(L[n+i]+R[n+i]>=i)X+=(min(i,L[n+i])-max(0,-R[n+i]+i)+1);
		//X+=min(L[n+1]+1,min(R[n+1]+1,i+1));
		//cout<<i<<" "<<X<<"\n";
	}
	
	cout<<2*n+1<<" "<<X;
	
	
	
return 0;
}