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
104
105
106
107
108
109
110
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e6+7;

int pozycja[MAX];

int liczmax(const vector <int>& maxy, int v)
{
    auto it = upper_bound(maxy.begin(), maxy.end(), v);
    return (it - maxy.begin());
}

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

    int n;
    cin >> n;

    vector <int> perm(n);
    vector <int> maxprawo(n);
    vector <int> maxlewo(n);
    long long lewo = 1, prawo = 1;
  
    for (int i = 0; i < n; ++i)
    {
        auto& x = perm[i];
        cin >> x;
        pozycja[x] = i;
    }

    maxprawo[n - 1] = perm[n - 1];
    maxlewo[0] = perm[0];

    for (int i = n - 2; i >= 0; --i)
    {
        maxprawo[i] = max(maxprawo[i + 1], perm[i]);
    }

    for (int i = 1; i < n; ++i)
    {
        maxlewo[i] = max(maxlewo[i - 1], perm[i]);
    }

    int mid2 = n + 1;
    
    reverse(maxprawo.begin(), maxprawo.end());

    long long res = 1;

    for (int i = 1; i < n; ++i)
    {
        int staryres = res;
        // cout << "licze " << i << "\n";

        int konieczne = i;
        int spelnione = i;
        int poz = pozycja[i];

        if (poz < pozycja[n])
        {
            konieczne = maxlewo[poz];
            spelnione = poz + 1;
            
            int potrzebne = 0;
            if (2 * konieczne >= mid2)
                potrzebne = max(0, 2 * konieczne + 2 - mid2 - spelnione);

            int ok = liczmax(maxprawo, konieczne);

            int roznica = ok - potrzebne;

            res += max(roznica + 1, 0);

            // cout << "potrzebuje " << konieczne << "\n";
            // cout << "mam " << spelnione << "\n";
            // cout << "pozostalo " << potrzebne << "\n";
            // cout << "z drugiej strony " << ok << "\n";
            // cout << "dostalem " << res - staryres << "\n";
        }
        else
        {
            konieczne = maxprawo[n - 1 - poz];
            spelnione = n - poz;
            int potrzebne = 0;
            
            if (2 * konieczne >= mid2)
                potrzebne = max(0, 2 * konieczne + 2 - mid2 - spelnione);

            int ok = liczmax(maxlewo, konieczne);
            int roznica = ok - potrzebne;

            res += max(roznica + 1, 0);

            // cout << "potrzebuje " << konieczne << "\n";
            // cout << "mam " << spelnione << "\n";
            // cout << "pozostalo " << potrzebne << "\n";
            // cout << "z drugiej strony " << ok << "\n";
            // cout << "dostalem " << res - staryres << "\n";
        }
    }

    cout << (n + 1) + n << " " << res << "\n";

    return 0;
}