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
80
81
#include<iostream>

using namespace std;

#define MAXN 1000002
#define ULL unsigned long long 

int n;
int loc[MAXN];

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n;
	for(int i = 0; i < n; i++) {
		int v;
		cin >> v;
		loc[v] = i;
	}

	ULL res = 1ll;

	int nloc = loc[n];
	int left = nloc, right = nloc;
	// int leftok = 0, rightok = 0;
	int ok = 0;
	int others;

	for(int i = 2 * n - 1; i > 0; i--) {
		int credits = n - (i + 1) / 2;
		if(i % 2 == 1) {
			int add = (i - 1) / 2;
			// cout << "trying " << add << ".5" << endl; 
			int l = loc[add];
			// cout << "found " << add << " at " << l << endl;
			ok++;
			if(l > nloc) {
				// rightok++;
				if(right < l) {
					right = l;
				}
			} else {
				// leftok++;
				if(left > l) {
					left = l;
				}
			}
			others = right - left - ok;
			if(others <= credits) {
				int free = credits - others;
				int fleft = left;
			       	int fright = n - (right + 1);
				// cout << "free: " << free << endl;
				if(fleft + fright < free) {
					break;
				}
				int ways = max(0, min(free, min(fleft, fright)) - max(0, free - max(fleft, fright)));
				res += 1ll + ways;
				// cout << "can make " << add << ".5" << " in " << ways << " ways" << endl;
			} 
		} 
		else {
			// cout << "trying " << i / 2 << endl; 
			if(others <= credits) {
				int free = credits - others;
				int fleft = left;
			       	int fright = n - (right + 1);
				// cout << "free: " << free << endl;
				if(fleft + fright < free) {
					break;
				}
				int ways = max(0, min(free, min(fleft, fright)) - max(0, free - max(fleft, fright)));
				res += 1ll + ways;
				// cout << "can make " << i / 2 << " in " << ways << " ways" << endl;
			}
		}

		// cout << "r, l, ok: " << right << " " << left << " " << ok << endl;
		// cout << "others: " << others << ", credits: " << credits << endl;
	}
	cout << n + n + 1 << ' ' << res << endl;
}