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
#include <stdio.h>
using ll=long long;
const int C=1000001;

int pos[C];
int main(){
	int n, i, a, next, span, leftmost=1000000000, rightmost=-1, to_push;
	scanf ("%d", &n);
	for (i=0; i<n; i++){
		scanf ("%d", &a);
		pos[a] = i;
	}

	ll res=0, cur=n, lefty, righty;
	for (i=0; i<=n; i++){ //iterate by size
		if (i%2 == 0){
			next = pos[cur];
			cur--;
			if (next<leftmost) leftmost=next;
			if (next>rightmost) rightmost=next;
		}
		span = rightmost-leftmost;

		if (span >= i) continue;
		else{
			lefty = rightmost-i+1;
			if (lefty < 0) lefty = 0;
			righty = leftmost+i-1;
			if (righty >= n) righty = n-1;

			res += righty-lefty-i+2;
		}
	}
	printf ("%d %lld\n", 2*n+1, res);

return 0;}