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
//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 7;
int n, lf, rg;
int t[N];
int p[N];
long long odp;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &t[i]);
		p[t[i]] = i;
		if (t[i] == n) {
			lf = rg = i;
		}
	}
	t[0] = t[n + 1] = -1e9;
	for (int i = n; i; --i) {
		//~ printf("%d: %d\n", i, i + (n - i) / 2);
		lf = min(lf, p[i + (n - i) / 2]);
		rg = max(rg, p[i + (n - i) / 2]);
		//~ printf("(%d %d)\n", lf, rg);
		if (rg - lf <= n - i) {
			//~ printf("ODP += %d - %d\n", min(lf, n - (n - i + 1) + 1), max(0, rg - (n - i + 1)));
			odp += max(0, min(lf, n - (n - i + 1) + 1) - max(0, rg - (n - i + 1)));
		}
	}
	printf("%d %lld\n", n + n + 1, odp);
	return 0;
}