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
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define fi first
#define se second
#define ll long long
#define ld long double
#define pb push_back
#define vi vector<int>
#define MAXN 100001

using namespace std;

struct dummy_set {
    int mi = INT32_MAX, ma = 0;
    int cnt = 0;
    int len;
    int n;

    void push(int v) {
        mi = min(mi, v);
        ma = max(ma, v);
        len = ma - mi + 1;
        cnt++;
    }

    ll res(int l) {
        if (len > l)
            return 0;

        int f = l - len;
        int fl = min(f, mi);
        int fr = min(f, n - ma - 1);
        int window = fl + fr;
        // if (v) {
        //     cout << "\t" << f << " " << fl << " " << fr << endl;
        // }

        ll res = fl + fr - f + 1;
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> A(n);
    vector<int> V(n + 1);

    for (int i = 0; i < n; i++) {
        cin >> A[i];
        V[A[i]] = i;
    }

    // for (int i = 0; i < n; i++)
    //     cout << i << " ";
    // cout << endl;
    // for (int i = 0; i < n; i++)
    //     cout << A[i] << " ";
    // cout << endl;

    dummy_set r;
    r.n = n;
    int elem = n;
    ll res = 0;

    for (int l = 1; l <= n; l++) {
        int expected = l / 2 + 1;
        while (r.cnt < expected) {
            r.push(V[elem]);
            elem--;
        }

        res += r.res(l);
        // cout << l << endl;
        // cout << "\t" << r.mi << " " << r.ma << endl;
        // cout << "\t" << r.cnt << " " << r.len << endl;
        // ll xx = r.res(l, true);
        // cout << "\t" << xx << endl;
    }

    int m = 2 * n + 1;
    cout << m << " " << res << endl;

    return 0;
}