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

constexpr int N = 1000 * 1000 + 1;

int positions[N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int num;
        scanf("%d", &num);
        positions[num] = i;
    }
    int req_min = positions[n], req_max = positions[n], req_len;
    long long result = 0;
    for (int len = 1; len <= n; ++len) {
        if ((len & 1) == 0) {
            req_min = std::min(req_min, positions[n - len/2]);
            req_max = std::max(req_max, positions[n - len/2]);
        }
        req_len = req_max - req_min + 1;
        if (req_len <= len) {
            int possible_min = std::max(1, req_min - (len - req_len));
            int possible_max = std::min(n, req_max + (len - req_len));
            result += ((possible_max - possible_min + 1) - len + 1);
        }
    }
    printf("%d %lld\n", 2 * n + 1, result);
    return 0;
}