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
73
74
75
76
77
78
#include <iostream>
#include <vector>
#include <utility>

unsigned long long difference(std::pair<int, int> const &range, int length, int rankSize)
{
    int distance = range.second - range.first + 1;
    if (distance > length)
        return 0;
    if (distance == length)
        return 1;

    int diff = length - distance;
    int left_start = std::max(range.first-diff,0);
    int left_end = std::min(range.second+diff, rankSize-1) - length + 1;
    return left_end - left_start + 1;
}

void solve(std::vector<int> &ranks)
{
    int maxFunc = 1 + ranks.size() * 2;
    if (ranks.size() == 1)
    {
        std::cout << maxFunc << " 1" << std::endl;
        return;
    }
    std::vector<int> indexes(ranks.size(), 0);
    for (int i = 0; i < ranks.size(); ++i)
        indexes[ranks.at(i) - 1] = i;

    std::vector<std::pair<int, int>> ranges(ranks.size(), {0, 0});
    ranges[ranks.size() - 1] = {indexes.back(), indexes.back()};
    for (int i = ranges.size() - 2; i >= 0; --i)
    {
        ranges[i] = {std::min(indexes[i], ranges[i + 1].first), std::max(indexes[i], ranges[i + 1].second)};
    }
    // for (auto const &index : ranges)
        // std::cout << "(" << index.first << "," << index.second << ") ";
    // std::cout << std::endl;

    unsigned long long count = 2;
    int stop = ranges.size() / 2;
    if (ranges.size() % 2 == 1)
        stop = (ranges.size() - 1) / 2;
    for (int i = ranges.size() - 2; i >= stop; --i)
    {
        int length = 2 * (ranges.size() - i - 1);
        auto range = ranges.at(i);
        int distance = range.second - range.first + 1;
        count += difference(range, length, ranges.size());

        length++;
        if (i == stop && ranges.size() % 2 == 1)
            break;
        count += difference(range, length, ranges.size());
    }

    std::cout << maxFunc << " " << count << std::endl;
}

int main()
{
    int n;

    std::cin >> n;
    std::vector<int> ranks;
    ranks.reserve(n);
    for (int i = 0; i < n; ++i)
    {
        int tmp;
        std::cin >> tmp;
        ranks.push_back(tmp);
    }

    solve(ranks);

    return 0;
}