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
#include <stdio.h>

#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))

#define MAX_N 1000000

int where[MAX_N+1];

int main(void)
{
	int n;
	int i;
	int w;
	long long ans = 0;
	int left, right;
	int left_lim, right_lim;

	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		int a;
		scanf("%d", &a);
		where[a] = i;
	}

	ans = 1;
	left = right = where[n];
	for (i = 2; i <= n; i++) {
		w = where[n - i/2];
		left = min(left, w);
		right = max(right, w);
		left_lim = max(1, right - i + 1);
		right_lim = min(n - i + 1, left);
		if (left_lim <= right_lim)
			ans += right_lim - left_lim + 1;
	}
	printf("%d %lld\n", 2 * n + 1, ans);

	return 0;
}