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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>

using integ = int_fast64_t;

struct Range {
    integ l;
    integ r;

    integ length() const {
        // l and r are inclusive, as in problem description, hence the +1
        return r - l  + 1;
    }
};

int main() {
    integ n;

    std::cin >> n;

    // Read the numbers
    std::vector<integ> ratings(n);
    std::vector<integ> inds(n + 1);
    for(integ i = 0; i < n; ++i) {
        std::cin >> ratings[i];
        // The index of the rating
        inds[ratings[i]] = i;
    }
    // The max is attainable for subsets of size k that contain all the k biggest numbers
    // i.e. the max numuer alone and the full set are always valid subsets

    // Look for any other possibilities
    integ l = inds[n];
    integ r =  inds[n];
    // Find the l and r containing the k langest numbers for each k
    std::vector<Range> ranges(n / 2 + 2);
    for(integ k = 1; k <= n / 2 + 1; ++k) {
        const integ kthHighest = n - k + 1;
        const integ ind = inds[kthHighest];
        // Get the range required to cover the k greatest numbers
        l = std::min(l, ind);
        r = std::max(r, ind);
        ranges[k] = {l, r};
        //std::cout << k << ": " << kthHighest << " " << l << " " << r << " -> " << ranges[k].length() <<  std::endl;
    }

    integ numPossib = 0;
    // Check how many ranges of length j (1 <= j <= n) can be valid
    for(integ j = 1; j <= n; ++j) {
        // The necessary number of highest numbers to be within an interval of enght j
        const integ necc = j / 2 + 1;
        const auto& range = ranges[necc];
        // Region from minimum possible l to maximum possible r of a valid region
        const Range maxRegion { std::max(0L, range.r - j + 1),
                                std::min(n - 1, range.l + j - 1) };
                                

        // Number of possible placemewnts of a valid inteval of ength j
        numPossib += std::max(0L, maxRegion.length() - j + 1);
        
        //std::cout << j << ": " << necc << " l="<< maxRegion.l << " " << maxRegion.r << " -> "
        //    << std::max(0L, maxRegion.length() - j + 1) << " (" << range.l << " " << range.r << ")" << "\n";
    }

    // The max value is known
    std::cout << 2 * n + 1 << " " << numPossib << std::endl;

    return 0;
}