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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

bool desc(int a, int b) {
    return a > b;
}


typedef long long ll;

#define MP(a, b) make_pair(a,b)

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

    ll n, a;
    vector<ll> nums;
    cin >> n;

    vector<ll> pos(n + 1);
    for (ll i = 1; i <= n; i++) {
        cin >> a;
        nums.push_back(a);
        pos[a] = i;
    }

//    cout << "nums: " << endl;
//    for (const auto &num: nums) {
//        cout << num << ", ";
//    }
//    cout << endl;

//    for (const auto &p: pos) {
//        cout << p << ", ";
//    }
//    cout << endl;

    vector<pair<pair<ll, ll>, ll>> ranges;

    ll from, to, dist;
    from = pos[n];
    to = pos[n];

    ranges.push_back(MP(MP(from, to), 0));

//    cout << "from: " << from << ", to: " << to << endl;
    for (ll i = n - 1; i >= 1; i--) {
//        cout << "extending to have: " << i << endl;
        ll count = n - i + 1;
        ll max_size = count * 2 - 1;
        from = min(from, pos[i]);
        to = max(to, pos[i]);
//        cout << "new range: [" << from << ", " << to << "]" << endl;
        ll size = to - from + 1;
//        cout << "range size: " << size << endl;
//        cout << "max size: " << max_size << endl;
        if (size <= max_size) {
            ll distance = max_size - size;
//            cout << "fits, distance: " << distance << endl;
            ranges.push_back(MP(MP(from, to), distance));
        }
    }

    set<pair<ll, ll>> sols;


//    cout << "ranges: " << endl;
    for (const auto &range: ranges) {
        from = range.first.first;
        to = range.first.second;
        dist = range.second;
//        cout << "[ " << from << ", " << to << " ]; dist: " << dist << endl;

        if (dist == 0) {
            sols.insert(MP(from, to));
        } else {
            for (ll d = 0; d <= dist; d++) {
//                cout << "considering dist: " << d << endl;
                for (ll l = max(from - d, 1LL); l <= from; l++) {
                    ll r = min(n, l + to - from + d);
//                    cout << "inserting: " << l << ", " << r << endl;
                    sols.insert(MP(l, r));
                }
            }
        }
    }

//    cout << "sols: " << endl;
//    for (const auto &sol : sols) {
//        cout << sol.first << ", " << sol.second << "; ";
//    }
//    cout << endl;


    cout << n * 2 + 1 << " " << sols.size();

    return 0;
}