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
// Autor: Mikołaj Janusz
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    ll n; cin >> n;
    vector<ll> numbers(n), numbers_indexes(n+1);

    for (ll i = 0; i < n; i++) {
        cin >> numbers[i];
        numbers_indexes[numbers[i]] = i;
    }

    ll median = (n + 1) / 2, window_size = 0, result = 0, 
       lower_bound = numbers_indexes[n], upper_bound = numbers_indexes[n]; 

    for (ll i = 0; i <= n / 2; i++) {
        lower_bound = (numbers_indexes[n-i] < lower_bound) ? numbers_indexes[n-i] : lower_bound;
        upper_bound = (numbers_indexes[n-i] > upper_bound) ? numbers_indexes[n-i] : upper_bound;
        window_size = upper_bound - lower_bound + 1;

        ll short_subarr = i*2;
        if (short_subarr <= n && window_size <= short_subarr) {
            if (window_size == short_subarr || (window_size != short_subarr && (lower_bound == 0 || n - upper_bound - 1 == 0)))
                result++;
            else if (upper_bound - short_subarr + 1 < 0 && lower_bound + short_subarr > n)
                result += n - short_subarr + 1;
            else if (upper_bound - short_subarr + 1 < 0 || lower_bound + short_subarr > n)
                result += min(lower_bound, n - upper_bound - 1) + 1;
            else
                result += short_subarr - window_size + 1;
        }
        
        ll long_subarr = short_subarr + 1;
        if (long_subarr <= n && window_size <= long_subarr) {
            if (window_size == long_subarr || (window_size != long_subarr && (lower_bound == 0 || n - upper_bound - 1 == 0)))
                result++;
            else if (upper_bound - long_subarr + 1 < 0 && lower_bound + long_subarr > n)
                result += n - long_subarr + 1;
            else if (upper_bound - long_subarr + 1 < 0 || lower_bound + long_subarr > n)
                result += min(lower_bound, n - upper_bound - 1) + 1;
            else
                result += long_subarr - window_size + 1;
        }
    }

    cout << (2 * n + 1) << " " << result << endl;
    return 0;
}