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

int indeksy[1000000]; // liczba-1 (0…N) => położenie na liście (0…N)

int main()
{
    int N;
    scanf("%d", &N);
    for (int i=0; i<N; ++i) {
        int A; scanf("%d", &A);
        indeksy[A-1] = i; // wartości będą od 0 do N-1
    }

    int min_index = INT_MAX, max_index = INT_MIN;
    unsigned long result = 0;
    int max_l_ogarniete = 0;
    for (int r=N-1; r>=0; --r) {
        min_index = std::min(min_index, indeksy[r]);
        max_index = std::max(max_index, indeksy[r]);
        int min_l = max_index - min_index + 1; // minimalna długość przedziału zawierającego wszystkie wartości od N-1 do r
        int max_l = std::min(N, 2*(N-r)-1); // maksymalna długość przedziału, który możemy skomponować z tych wartości
        for (int l=std::max(min_l, max_l_ogarniete+1); l<=max_l; ++l) {
            int min_pos_left = std::max(min_index-(l-min_l), 0);
            int max_pos_right = std::min(max_index+(l-min_l), N-1);

            result += 2+max_pos_right-min_pos_left - l;
            max_l_ogarniete = l;
        }
    }
    printf("%d %lu\n", 2*N+1, result);
}