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

int n;
long long out;  
int scores[1000009];
int idx[1000009];

int main() {
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> scores[i];
        idx[scores[i]] = i;
    }
    cout << 2*n+1 << " ";
    int l = idx[n], r = idx[n];
    out = 1;
    for(int i=2; i<=n; i++) { // potrzebujemy i największych wartości, dopuszczamy przedziały wielkości 2x-2, 2x-1
        int to_add = idx[n-i+1];
        if(l > to_add) l = to_add;
        if(r < to_add) r = to_add;
        int interval_size = r-l+1;
        if(interval_size <= 2*i-2) {
            if(2*i-2 > n) break;
            int to_left = min(2*i-2-interval_size,l);
            int to_right = min(2*i-2-interval_size,n-1-r);
            out += to_left+interval_size+to_right-(2*i-2)+1;
            // cout << i << ", " << out << endl;
        }
        if(interval_size <= 2*i-1) {
            if(2*i-1 > n) break;
            int to_left = min(2*i-1-interval_size,l);
            int to_right = min(2*i-1-interval_size,n-1-r);
            out += to_left+interval_size+to_right-(2*i-1)+1;
            // cout << i << ", " << out << endl;
        }
    }
    cout << out << endl;
}