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
#include <stdio.h>
#include <algorithm>
typedef long long ll;
int main(void) {
	size_t N; scanf("%lu", &N);
	size_t *arr = new size_t[N];
	size_t *locations = new size_t[N+1];
	size_t L, R;
	for (size_t i = 0; i < N; ++i) {
		scanf("%lu", &arr[i]);
		locations[arr[i]] = i;
		if (arr[i] == N) {
			L = i; R = i;
		}
	}

	bool *present = new bool[N+1]{};
	present[N] = true;
	size_t possibilities = 1;
	size_t m = N-1;
	while (m >= N/2 + N%2) {
		if (locations[m] < L) {
			for (size_t i = locations[m]; i < L; ++i)
				present[arr[i]] = true;
			L = locations[m];
		}
		if (locations[m] > R) {
			for (size_t i = R+1; i <= locations[m]; ++i)
				present[arr[i]] = true;
			R = locations[m];
		}

		size_t interval_current = R-L+1;
		for (size_t interval_required = 2*(N-m), i=0; i<2 && interval_required <= N; ++i, ++interval_required) {
			if ( interval_current == interval_required )
				++possibilities;
			else if ( interval_current < interval_required ) {
				size_t beg_l = std::max(0ll, (ll)R - (ll)interval_required + 1ll);
				size_t end_l = L;
				size_t beg_r = beg_l + interval_required-1;
				size_t end_r = std::min(end_l + interval_required-1, N-1);
				if (end_r >= beg_r)
					possibilities += end_r - beg_r + 1;
			}
		}

		// size_t minimal_required = N - (R-L+1)/2;
		// if (present[minimal_required]) ++possibilities;
		--m;
	}

	// L = std::min(L, locations[m]);
	// R = std::max(R, locations[arr[m]]);

	// for (size_t k = 2; k <= N; ++k) {
	// 	if (k % 2 == 0) {
	// 		if (L > 0 && arr[L-1] == m-1) L -= 1;
	// 		else if (R < N-1 && arr[R+1] == m-1) R += 1;
	// 	} else {
	// 	}
	// }

	printf("%lu %lu\n", 2*N+1, possibilities);
	return 0;
}