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
#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;

const int P = 1000000000 + 7;

int main() {
    std::ios::sync_with_stdio(false);
    int n, x;
    cin >> n;
    vector<int> ranks;
    set<int> visited;
    unordered_map<int, int> rank_idx;
    for(int i = 0; i < n; ++i) {
        cin >> x;
        ranks.push_back(x);
        rank_idx[x] = i;
    }
    int left = rank_idx[n], right = rank_idx[n];
    long long solutions = 0;
    visited.insert(n);
    for(int next = n; next >= (n + 1) / 2; --next) {
        if(visited.find(next) == visited.end()) {
            int next_pos = rank_idx[next];
            while(next_pos < left) {
                --left;
                visited.insert(ranks[left]);
            }
            while(next_pos > right) {
                ++right;
                visited.insert(ranks[right]);
            }
        }

        int desired_size, missing, window;
        if(2 * next != n) {
            desired_size = 2 * (n - next) + 1; // 1-element median
            missing = desired_size - visited.size();
            if(missing >= 0) {
                window = min(missing, left) + min(missing, n - right - 1);
                solutions += window - missing + 1;
            }
        }

        if(next < n) {  // 2-elements median
            desired_size = 2 * (n - next - 1) + 2;
            missing = desired_size - visited.size();
            if(missing >= 0) {
                window = min(missing, left) + min(missing, n - right - 1);
                solutions += window - missing + 1;
            }
        }
    }
    cout << 2 * n + 1 << " " << solutions << endl;
}