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 <cstdlib>
#include <vector>

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

    std::vector<int> pos(n+1);
    for (int i = 0; i < n; ++i) {
        int t;
        scanf("%d", &t);
        pos[t] = i;
    }

    unsigned long long count = 0ULL;

    int i = pos[n];
    int j = pos[n];
    for (int d = 0; d < n; ++d) {

        if (d % 2 == 1) 
        {
            int t = n - (d+1)/2;
            int t_pos = pos[t];

            i = std::min(i, t_pos);
            j = std::max(j, t_pos);
        } 

        int ii = std::max(0, j - d);
        unsigned long long delta = std::max(0, std::min(n - (ii + d), i - ii + 1));
        count += delta;
    }

    printf("%d %llu\n", 2*n + 1, count);

    return 0;
}