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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int INF = 1 << 30;
    int n;
    cin>>n;
    vector< pair<int,int> > a;
    for(int i=0; i<n; ++i) {
        int A;
        cin>>A;
        a.push_back(make_pair(A,i));
    }
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    vector<int> L,P;
    L.push_back(a[0].second);
    P.push_back(a[0].second);
    for(int i=1; i<n; ++i) {
        if(a[i].second > P[i-1]) {
            P.push_back(a[i].second);
            L.push_back(L[i-1]);
        }
        else if(a[i].second < L[i-1]) {
            L.push_back(a[i].second);
            P.push_back(P[i-1]);
        }
        else {
            L.push_back(L[i-1]);
            P.push_back(P[i-1]);
        }
    }
    long long ans = 0;
    for(int m=1; m<=n; ++m) {
        int T;
        if(m % 2 == 1) T = (2*n-m+1) / 2;
        else T = (2*n-m) / 2;
        if(P[n-T] - L[n-T] + 1 <= m) ans += m - P[n-T] + L[n-T] - max(m - n + L[n-T],0) - max(m - P[n-T] - 1,0);
        //cout<<ans<<" ";
    }
    //cout<<endl;
    cout<<(n+n+1)<<" ";
    cout<<ans<<endl;
    
    
    return 0;
}