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
#include "bits/stdc++.h" // Ignacy Boehlke
using namespace std;     // XIII LO Szczecin
template<class A, class B> ostream& operator << (ostream& os, const pair<A, B>& p) {return os << '{' << p.first << ", " << p.second << '}';}
template<class T> auto operator << (ostream& os, const T& v) -> decltype(v.begin(), os) {os << '{';for (auto i : v) os << i << ", ";return os << '}';}
#ifdef DEBUG
#define D(x...) x
#else
#define D(x...)
#endif
#define LN(x) D(cerr << #x << ": " << x << ' ')
#define LOG(x) D(cerr << #x << ": " << x << '\n')
#define ssize(x) ((int)x.size())
#define FOR(a, b, c) for(int a = (b); a <= (c); ++a)
#define REP(a, b) FOR(a, 0, b - 1)
#define ALL(x) (x).begin(), (x).end()
#define fi first
#define se second
using ll = long long;

#define SUM(a, b) ((ll)((a) + (b)) * ((b) - (a) + 1) / 2)
int main() {
    int n;
    scanf("%d", &n);
    int a[n], pos[n + 1];
    pos[0] = -1;
    REP(i, n) scanf("%d", &a[i]), pos[a[i]] = i;
    pair<int, int> curr = {pos[n], pos[n] - 1};
    ll res = 0;
    for (int i = n; i >= 1; --i) {
        if (curr.se < pos[i]) curr.se = pos[i];
        else if (pos[i] < curr.fi) curr.fi = pos[i];
        if (curr.fi < pos[i - 1] && pos[i - 1] < curr.se) continue;

        int d1 = curr.fi;
        if (pos[i - 1] < curr.fi) d1 = min(d1, curr.fi - pos[i - 1] - 1);
        int d2 = n - curr.se - 1;
        if (curr.se < pos[i - 1]) d2 = min(d2, pos[i - 1] - curr.se - 1);
        int x = 2 * (n - i) - (curr.se - curr.fi);
        if (x < 0) continue;
        d1 = min(d1, x);
        d2 = min(d2, x);
        LN(i); LN(x); LN(curr); LN(d1); LOG(d2);

        //FOR(j, 0, d1) res += min(x - j + 1, d2 + 1);
        res += max(0LL, (ll)min(d1 + 1, x - d2) * (d2 + 1)) + max(0LL, SUM(x - d1 + 1, min(x + 1, d2 + 1)));
        LOG(res);
    }
    printf("%d %lld\n", n * 2 + 1, res);
}