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

using namespace std;

int tab[1000001];
int poz[1000001];
int n, d;

long long get_local_score(int l, int r, int len) {
	if (r - l + 1 > len) {
		return 0L;
	} 
	int tmp1, tmp2, tmp3;
	tmp1 = l;
	tmp2 = n-r - 1;
	tmp3 = len - r + l - 1;
	if (tmp3 <= min(tmp1, tmp2)) {
		return (long long) (tmp3 + 1);
	} else if (tmp3 <= max(tmp1, tmp2)) {
		return (long long) (min(tmp1, tmp2) + 1);
	} else {
		return (long long) (tmp1 + tmp2 - tmp3 + 1);
	}
	
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=0; i < n; i++) {
    	cin >> d;
    	tab[i] = d;
    	poz[d] = i;
    }

    int l=poz[n];
    int r=poz[n];
    int core_size = 1;
    int max_in_core = n;
    long long out = 1;
    for(int k=1; k<=n/2; k++) {
    	max_in_core--;
    	int n_poz = poz[max_in_core];
    	if (n_poz < l) {
    		l=n_poz;
    	} else if (n_poz > r) {
    		r=n_poz;
    	}
    	// cout << "core: " << l << " " << r << endl;

    	// process 2k
    	out += get_local_score(l, r, 2 * k);
    	// cout << 2 * k << ": " << out << endl;
    	// process 2k+1
    	if (2 * k + 1 <= n) {
    		out += get_local_score(l, r, 2 * k + 1);
    	}
    	// cout << 2 * k + 1 << ": " << out << endl;
    }
    cout << 2 * n + 1 << " " << out;

    return 0;
}