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
#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
    int N;
    scanf("%d", &N);

    std::vector<int> position(N+1, -1);
    for (int i=1; i<=N; ++i) {
        int x;
        scanf("%d", &x);
        position[x] = i;
    }

    int lhs = position[N];
    int rhs = position[N];
    long long int result = 0;
    int bigcnt = 1;

    for (int len=1; len<=N; ++len) {
        int big = len/2 + 1;
        while (bigcnt < big) {
            int val = N-bigcnt;
            lhs = std::min(lhs, position[val]);
            rhs = std::max(rhs, position[val]);
            bigcnt++;
        }

        int cnt = rhs-lhs+1;
        if (cnt <= len) {
            int begin = lhs-1;
            int end = N-rhs;
            result += std::min(std::min(begin+1-std::max(0, len-end-cnt), end+1-std::max(0, len-begin-cnt)), len-cnt+1);
        }
    }

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