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
#include <cstdio>

const int N = 1000000 + 9;

int nextInt() { int n; scanf("%d", &n); return n; }

int v[N];
int pos[N];

int main() {
	int n = nextInt();
	v[0] = v[n + 1] = -1;
	for (int i = 1; i <= n; ++i) {
		v[i] = nextInt();
		pos[v[i]] = i;
	}

	int a = pos[n];
	int b = a + 1;

	int f = n + n + 1;
	long long cnt = 0;

	for (int s = 1; s <= n; ++s) {
		int vmin = n - s / 2;
		if (pos[vmin] < a) a = pos[vmin];
		if (pos[vmin] >= b) b = pos[vmin] + 1;
		//fprintf(stderr, "s %d => a,b %d %d\n", s, a, b);

		if (b - a > s) continue;

		int left = a - 1;
		int right = n + 1 - b;
		int todo = s - (b - a);
		int leftLost = 0; if (todo > left) leftLost = todo - left;
		int rightLost = 0; if (todo > right) rightLost = todo - right;
		int lost = leftLost + rightLost;
		if (lost > todo) lost = todo + 1;
		int add = todo + 1 - lost;
		//fprintf(stderr, "s %d => add %d\n", s, add);
		cnt += add;
	}

	printf("%d %lld\n", f, cnt);


	return 0;
}