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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <cstdlib>
#include <cassert>

#include <algorithm>

static const size_t MAX_N = 1000 * 1000;

// int arr[MAX_N];
int invarr[MAX_N];

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

    for (int i = 0; i < n; i++) {
        int a;
        assert(1 == scanf("%d", &a));
        a--;
        invarr[a] = i;
    }

    long long int solutions = 0;

    int left_bound = invarr[n - 1];
    int right_bound = invarr[n - 1] + 1;
    for (int i = 1; i <= n; i++) {
        const int x = invarr[n - i];
        left_bound = std::min(left_bound, x);
        right_bound = std::max(right_bound, x + 1);

        const int interval_size = right_bound - left_bound;

        // const int target_interval_size = 2 * i - 2;

        // Case 1: two smallest elements of our sequence are the median
        auto compute_for_size = [&] (int target_interval_size) -> int {
            const int to_add = target_interval_size - interval_size;
            if (to_add < 0) {
                return 0;
            }
            const int begin_bound = std::max(0, left_bound - to_add);
            const int end_bound = std::min(n, right_bound + to_add);
            return std::max(0, end_bound - begin_bound - target_interval_size + 1);
        };

        solutions += compute_for_size(2 * i - 2);
        solutions += compute_for_size(2 * i - 1);
    }

    printf("%d %lld\n", 2 * n + 1, solutions);

    return 0;
}