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
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

constexpr int N = 1 << 20;
int t[N];
int p[N];
int n;
int mn, mx, req, curr;
lld res, begg, endd, add;

int main(){
	scanf("%d", &n);
	
	for(int i = 1; i <= n; ++i) {
		scanf("%d", t + i);
		p[t[i]] = i;
	}
	
	mn = p[n];
	mx = p[n];
	req = n;
	curr = 1;
	res = 1;
	
	for (int i = n - 1; i > 0; --i) {
		if (curr & 1) {
			--req;
			mn = min(mn, p[req]);
			mx = max(mx, p[req]);
		}
		++curr;
		
		//add = max(0, curr - mx + mn);
		//add = min(add, lld(n - mx + 1));
		//add = min(add, lld(mn));
		
		// start >= 1
		// start >= mx - curr + 1
		
		begg = max(1, mx - curr + 1);
		endd = min(n, mn + curr - 1);
		add = max(0ll, endd - begg + 2 - curr);
		
		//printf("%d: %d - %d, %d (%d), %lld\n", i, mn, mx, curr, req, add);
		
		res += add;
	}
	
	printf("%d %lld\n", n + n + 1, res);
	
	
	return 0;
}