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
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a, perm;
    a.resize(n);
    perm.resize(n + 1);
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        a[i] = k;
        perm[k] = i;
    }
    long long sum = 1;
    int l, r;
    l = r = perm[n];
    for (int s = 2; s <= n; ++s) {
        if (perm[n - s / 2] < l) l = perm[n - s / 2];
        if (perm[n - s / 2] > r) r = perm[n - s / 2];
        if (r - l > s - 1) continue;
        int to_add = s - (r - l);
        if (to_add > n - r) to_add = n - r;
        if (to_add > l + 1) to_add = l + 1;
        if (to_add > n - s + 1) to_add = n - s + 1;
        sum += to_add;
    }
    cout << 2 * n + 1 << ' ' << sum << '\n';
}