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>

const int maxN = 1e6 + 10;
int pos[maxN];
int N;


inline int max(int a, int b) { return a < b ? b : a; }
inline int min(int a, int b) { return a < b ? a : b; }

int main() {
    scanf("%d", &N);
    for (int x, i = 0; i < N; ++i) {
        scanf("%d", &x);
        pos[x] = i;
    }
    int mn = N + 1, mx = -1;
    int used = 0;
    long long result = 0;
    for (int n = 1; n <= N; ++n) {
        int K = n / 2 + 1;
        if (used < K) {
            mn = min(mn, pos[N - used]);
            mx = max(mx, pos[N - used]);
            used++;
        }

        int mxpos = min(mn + n - 1, N - 1);
        int mnpos = max(mx - n + 1, 0);
        int moves = min(N - n + 1, min(min(mn - mnpos + 1, mxpos - mx + 1),
                                       min(mn + 1, N - mx)));
        result += max(0, moves);
    }

    printf("%lld %lld\n", 2LL * N + 1, result);
}