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 <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

typedef long long int LL;

constexpr LL N = 1e6 + 7;
set <pair<LL,LL>> wieksze;
vector <pair<LL,LL>> poz;
LL tab[N], n, med, od, wyn=1,p,q,a,x, q1, p1;

inline LL podz() {
    // med - 1 w przedziale
    if(poz[x-1].second < p1 || poz[x-1].second > q1)
        return -1;
    return 2 + 2*(n - a) - (q1-p1+1);
}

inline LL n_podz() {
    return 1 + 2*(n - a) - (q-p+1);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie();
    int uj = 0;
    cin >> n;
    cout<<2*n+1<<" ";
    med = n/2 + 1;
    if( n % 2 == 0 ) {
        uj = 1;
        wyn--;
    } for(LL i=0;i!=n;i++)
        cin>>tab[i];
    for(LL i=0;i!=n;i++)
        if(tab[i] >= med - uj) {
            wieksze.insert({tab[i],i});
            poz.push_back({tab[i],i});
        }
    sort(poz.begin(),poz.end());
    for(LL i=1;i!=(LL)poz.size();i++) {
        a = poz[i].first; x = poz[i].second; p = x; q = x; x = i;
        while(!wieksze.empty() && wieksze.begin()->first <= a)
            wieksze.erase(wieksze.begin());
        while(!wieksze.empty()) {
            auto it = wieksze.end(); it--;
            if(it->first <= a)
                wieksze.erase(it);
            else break;
        } if(!wieksze.empty()) {
            auto it = wieksze.end(); it--;
            p = min(p,wieksze.begin()->second);
            q = max(q,it->second);
            p1 = min(p,poz[x-1].second); q1 = max(q,poz[x-1].second);
            LL s = podz();
            if(s >= 0)
                wyn += max((LL)1,2*min(min(n-q1-1,p1),s));
            s = n_podz();
            if(s >= 0)
                wyn += max((LL)1,2*min(min(n-q-1,p),s));
        }
    } if(n != 1) wyn++;
    if(abs(poz[poz.size()-2].second - poz.back().second) == 1) wyn++;
    cout<<wyn<<"\n";
    return 0;
}