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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
using namespace std;

int t[1000005];
int s1[4000005], s2[4000005], s3[4000005], s4[4000005];
int b1[1000005], b2[1000005];

int main(){
	int n, p;
	cin >> n;
	const int PREF = 2 * n + 1;
	for (int i = 0; i < n; i++){
		cin >> t[i];
		if (t[i] == n){
			p = i;
		}
	}
	int maxi = 0;
	int last = 0;
	for (int i = 0; i <= p; i++){
		if (t[i] > maxi){
			for (int l = maxi; l <= t[i]; l++){
				b1[l] = i;
			}
			maxi = t[i];
			//last = i;
		}
	}
	maxi = 0;
	for (int i = 0; i <= n; i++){
		b2[i] = n;
	}
	last = n;
	for (int i = n - 1; i >= p; i--){
		if (t[i] > maxi){
			for (int l = maxi; l <= t[i]; l++){
				b2[l] = i + 1;
			}
			//last = i;
			maxi = t[i];
		}
	}
	maxi = 0;
	long long res = 1;
	//int preCount = 1;
	for (int i = 0; i < p; i++){
		maxi = max(maxi, 2 * t[i]);
		//if (maxi >= n + 1 + i){
			int required = max(0, maxi - (n + 1) - i + 1);
			res += max(0, n - b2[maxi / 2] - required + 1);
			//cout << "(c, " << i << ", " << maxi << ", " << b2[maxi / 2] << ", " << required << ", " << n << ")\n";
			//cout << res << "\n";
		//}
		//else {
		//	preCount++;
		//	cout << "\na " << i << "\n";
		//	cout << res << "\n";
		//}
	}
	//cout << "wumwum " << preCount << "\n";
	maxi = 0;
	//res += preCount;
	for (int i = n - 1; i > p; i--){
		maxi = max(maxi, 2 * t[i]);
		//if (maxi >= n + 1 + (n - 1 - i)){
			int required = max(0, maxi - (n + 1) - (n - 1 - i) + 1);
			//cout << res << "\n";
			res += max(0, b1[maxi / 2] - required + 1);
		//	cout << "(d, " << i << ", " << b1[maxi/2] << ", " << required << ", " << maxi << " )\n";
	//		cout << res << "\n";
	//	}
	//	else {
	//		res += preCount;
	//		cout << "\nb " << i << "\n";
	//		cout << res << "\n";
//		}
	}
	cout << 2 * n + 1 << " " << res << "\n";
}