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
#include<cstdio>

static int tab[1000000];

int main(){
    int n;
    scanf("%i", &n);

    for(int i = 0; i < n; ++i){
        int a;
        scanf("%i", &a);

        tab[a-1] = i;
    }

    unsigned long long spos = 1;

    int b = tab[n-1];
    int e = tab[n-1];

    int curr = n-1;

    while(curr){
        --curr;
        int in = tab[curr];

        if(in < b){
            b = in;
        }
        else if(in > e){
            e = in;
        }

        if(e - b + 1 <= 2*(n - curr) - 1){
            int d = 2*(n - curr) - 1;
            int r = d - e + b - 1;
            int p = b - r;
            if(p < 0){
                p = 0;
            }
            int k = e + r;
            if(k > n - 1){
                k = n - 1;
            }

            if(k - p + 1 >= d){
                spos += k - p + 2 - d;
            }

            --d;
            r = d - e + b - 1;
            if(r < 0)
                continue;
            p = b - r;
            if(p < 0){
                p = 0;
            }
            k = e + r;
            if(k > n - 1){
                k = n - 1;
            }

            if(k - p + 1 >= d){
                spos += k - p + 2 - d;
            }
        }
    }


    printf("%i %llu\n", 2*n+1, spos);

    return 0;
}