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 <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int A[1000001], R[1000001];

long long sl(long long a) {
    if (a < 0) return 0;
    else return a*(a+1)/2;
}

int main() {
    int n, t;
    long long s = 1;
    scanf("%d", &n);
    for (int i=1;i<=n;i++) {
        scanf("%d", &t);
        A[i] = t;
        R[t] = i;
    }
    int l = R[n], r = R[n];
    //**/printf("1");
    for (int h=2;h<=n;h++) {
        int m = n - h/2;
        if (R[m] < l) l = R[m];
        if (R[m] > r) r = R[m];
        m = h-(r-l);
        if (m>0) {
            s += min(min(m, l), min(n+1-r, n+1-h));
            //printf(" + %d", min(min(m, l), min(n+1-r, n+1-h)));
        } //**/else printf(" + 0");
    }
    //**/printf(" = %lld", s);
    printf("%lld %lld", 1ll*n+(n+1), s);
}