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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n; cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; ++i) cin >> v[i];

    if(n==1)
    {
        cout << "3 1" << endl;
        return 0;
    }
    //for(int i=0; i<n; ++i) cout << v[i] << " "; cout << endl;

    vector<int> poz(n+1);
    for(int i=0; i<n; ++i) poz[v[i]]=i;
    //for(int i=1; i<=n; ++i) cout << poz[i] << " "; cout << endl;


    int mini = poz[n];
    int maxi = poz[n];
    int niep = 1;
    int rozm = 1;
    int pust = 0;

    int res = 1; // 'n'
    int can = 0; // tyle moze byc pustych
    set<pair<int,int>> s;
    s.insert(make_pair(mini,maxi));
    int n_low = (n%2==0? n/2: n/2+1);
    for(int i=n-1; i>=n_low; --i)
    {
        //cout << i << ": ";
        mini = min(mini, poz[i]);
        maxi = max(maxi, poz[i]);
        rozm = maxi - mini + 1;
        niep++;
        pust = rozm - niep;
        //cout << "mini=" << mini << " maxi=" << maxi << " rozm=" << rozm << " niep=" << niep << " pust=" << pust << endl;
        ++can;
        //cout << " can =" << can << endl;

        for(int j=0; j<=can-pust; ++j)
        {
            for(int k=0; k<=j; ++k)
            {
                int i1 = mini - j + k;
                if(i1<0) continue;

                int i2 = maxi + k;
                if(i2>n-1) break;

                //cout << i1 << " - " << i2 << endl;
                s.insert(make_pair(i1, i2));

            }

        }

    }
//    for(auto x:s)
//    {
//        for(int i=x.first; i<=x.second; ++i)
//            cout << v[i] << " ";
//        cout << endl;
//    }
    cout << 2*n+1 << " " << s.size() << endl;
}