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

typedef long long ll;
const ll SIZE = 1000004, inf = 1000000004;
ll n,t[SIZE],maxi,med = 0,poz[SIZE];
ll X = inf, Y = -1, wynik;

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
	cin>>n; maxi = 2*n+1;
	for(int i = 0; i < n; i++) cin>>t[i], med = max(med,2*t[i]), poz[t[i]] = i;
	for(ll i = med; i > 0; i--){
    // cerr<<"med = "<<i<<endl;
		ll a = i/2, b = i-a;
    // cerr<<"a = "<<a<<"    b = "<<b<<endl;
		ll d = maxi - i;
    if(d <= n){
      // cerr<<"aby dalo sie z mediany "<<i<<" zrobic "<<maxi<<" to d = "<<d<<endl;
    	X = min(X,poz[min(a,b)]), Y = max(Y,poz[min(a,b)]);
      // cerr<<"X = "<<X<<"   Y = "<<Y<<endl;
      //if(d == n) wynik++;
      //else if(Y-X+1 == d) wynik++, cerr<<"przedzial "<<d<<" elementowy od "<<X<<" do "<<Y<<" da sie pokryc na 1 sposob"<<endl;
      if(Y-X+1 <= d){
        ll x = max(0*1ll,Y-d+1), y = min(X,n-d);
        // cerr<<"na tyle sposobow moge pokryc "<<d<<"-elementowy przedzial od "<<X<<" do "<<Y<<": "<<y-x+1<<endl;
      	wynik+= y-x+1;
      }
    }
	}
	cout<<maxi<<" "<<wynik<<"\n";
	return 0;
}