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
/* 2021
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>

int scores;
int score;
int position[1048576];
long long int count;
int start;
int end;

int main(void)
{
    scanf("%d", &scores);
    for(int s = 0; s < scores; ++s)
    {
        scanf("%d", &score);
        position[score] = s + 1;
    }

    start = position[scores];
    end = position[scores];

    for(int len = 1; len <= scores; ++len)
    {
        score = scores - len / 2;
        start = std::min(start, position[score]);
        end = std::max(end, position[score]);

        if(end - start + 1 > len)
            continue;

        int wiggle = len - end + start - 1;
        count += 1 + std::min(std::min(start - 1, scores - len), std::min(scores - end, wiggle));
    }

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