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
// 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i, p, k) for(int i(p); i < (k); ++i)
typedef long long int ll;
typedef long double ld;
template <typename T = int> inline T in()
{
    T x;
    std::cin >> x;
    return x;
}
constexpr int maxn = 1e6 + 3;
int poz[maxn];
int main()
{
    std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0);
    int n(in());
    rep(i, 1, n+1)poz[in()] = i;
    std::cout << 2*n + 1<<' ';
    ll odp(0);
    int p(poz[n]), k(poz[n]);
    rep(i, 1, n+1)
    {
        if(!(i & 1))
        {
            int j(poz[n - i/2]);
            if(j < p)p = j;
            if(j > k)k = j;
        }
        odp += std::max(0, std::min(n-i+1, p) - std::max((k-i), 0));
    }
    std::cout << odp<<'\n';
    return 0;
}