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

typedef long long int lli;

const int MAXN = 1'000'005;

int t[MAXN];
int poz[MAXN];

int main() {
	int n;
	scanf("%d", &n);
	
	for (int i=0; i<n; i++) {
		scanf("%d", &t[i]);
		poz[t[i]] = i;
	}
	
	int min=poz[n], max=poz[n];
	lli res = 0;
	
	for (int l=1; l<=n; l++) {
// 		printf("l %d\n", l);
// 		printf("poz %d\n", n-l/2);
		min = std::min(min, poz[n-l/2]);
		max = std::max(max, poz[n-l/2]);
// 		printf("[%d %d]\n", min, max);
		
		if (max - min + 1 > l)
			continue;
		
		int minbeg = std::max(0, max-l+1);
		int maxbeg = std::min(min, n-l);
// 		printf("minbeg %d, maxbeg %d\n", minbeg, maxbeg);
// 		printf("add %d\n", maxbeg - minbeg + 1);
		res += maxbeg - minbeg + 1;
	}
	
	printf("%d %lld\n", 2*n+1, res);
	
	return 0;
}