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
#include<bits/stdc++.h>
using namespace std;

bool is_in_range(int l,int r,int c,vector<int> &where) {

    if(where[c] >= l && where[c] <=r)
        return true;
    return false;
}

void move_range(int &l, int &r,int c, vector<int> &where) {

    if(where[c] < l)
        l = where[c];
    if(where[c] > r)
        r = where[c];
    return;
}

int range_size(int l, int r) {

    return r-l+1;
}

int main() {

    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> vec(n);
    vector<int> where(n+1);
    for(int k=0;k<n;k++) {
        cin >> vec[k];
        where[vec[k]] = k;
    }
    if(n==1) {
        cout << 2*n +1 << " 1"<<endl;
        return 0;
    }
    else if(n==2) {
        cout << 2*n +1 << " 2" <<endl;
        return 0;
    }
    int l = where[n],r = where[n];
    long long ile = 1;
    for(int k = n-1; k>=(n+1)/2;k--) {

        //cout << "PRZESUWAM PRZEDZIAL" <<endl;
        move_range(l,r,k,where);
        //cout << " NOWE l = " << l << " " << " r = " << r <<endl;
        if(k != (n+1)/2 && is_in_range(l,r,k-1,where))
            continue;
        //cout << k-1 << " NIE NALEZY DO PRZEDZIALU" <<endl;
        int curr_size = range_size(l,r);
        int max_able_to_add = 2*(n-k+1)-1 -curr_size;
        //cout << "MAKSYMALNIE MG DODAC " << max_able_to_add <<endl;
        if(max_able_to_add < 0)
            continue;
        int max_r_index = min(n-1,r+max_able_to_add);
        int min_l_index = max(0,l-max_able_to_add);
        //cout << "MIN_L = " << min_l_index << " " << "MAX_R = " << max_r_index <<endl;
        if(k != (n+1)/2) {
            //cout << "check "<< min_l_index << " " << where[k-1] <<endl;
            if(where[k-1] > r)
                max_r_index = min(where[k-1]-1,max_r_index);
            if(where[k-1] < l )
                min_l_index = max(min_l_index,where[k-1]+1);
        }
        if(max_r_index - r < l - min_l_index) {
            for(int j=r;j <=max_r_index;j++) {
                //cout << "DODAJE " << min(max_able_to_add- + r - j +1,l-min_l_index+1) <<endl;
                ile += (long long)min(max_able_to_add+r - j +1,l-min_l_index+1);
            }
        }
        else {
            for(int j=l;j>=min_l_index;j--) {
                //cout << "DODAJE " << min(max_able_to_add + j - l +1,max_r_index - r +1) <<endl;
                ile += (long long) min(max_able_to_add + j - l +1,max_r_index - r +1);
            }
        }
    }
    cout << 2*n + 1 << " " << ile << endl;
}