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

#define FOR(i,a,b) for(int (i)=(int)(a); (i)!=(int)(b); ++(i))
typedef unsigned long long int ulli;

int n;
vector<int> A, pos;

int main() {
    scanf("%d", &n);
    A.resize(n);
    pos.resize(n);
    FOR(i,0,n) {
        scanf("%d", &A[i]);
        --A[i];
        pos[A[i]] = i;
    }

    ulli result = 1;
    int L = pos[n-1], R = pos[n-1], less_count = 0;
    int max_expected = 1, less_expected = 0;

    FOR(i,0,n-1) {
        if (i%2 == 0) {
            ++max_expected;
            int new_max_pos = pos[n-max_expected];
            if (new_max_pos < L) {
                less_count += (L - new_max_pos - 1);
                L = new_max_pos;
            } else if (new_max_pos > R){
                less_count += (new_max_pos - R - 1);
                R = new_max_pos;
            } else --less_count;
        } else ++less_expected;

        if (less_expected < less_count) continue;
        int extra = less_expected - less_count;
        int length = R - L + 1;
        int min_left = max(0, L - extra);
        int max_left = min(L, n - length - extra);
        result += (ulli)(max_left) - (ulli)(min_left) + 1;
    }

    printf("%d %llu\n", 2*n+1, result);
}