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
84
85
86
87
88
89
90
91
92
93
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>

using namespace std;

const int max_n = 1000020;

vector<int> t;
vector<int> tpos (max_n);
int n;
long long result;

void addresults(int l, int r, int maxsize)
{
        int size, df;
        int a,b;

        size = r-l+1;
        df = maxsize-size;
        a = max(0,l+maxsize-n);
        b = min(df,l);

        if (b-a+1 > 0) {
                result += b-a+1;
        }
}

void calc()
{
        int l, r, e;

        result = 0;
        l = r = tpos[n];
        result++;

//        printf("result (%d, %d)\n", l, r);

        if (n % 2 == 0) {
                e = n/2;
        } else {
                e = (n+1)/2;
        }

        for(int i = n-1; i >= e; --i) {
                int j, pos;
                pos = tpos[i];
                if (pos < l) {
                        l = pos;
                } else {
                        if (pos > r) {
                                r = pos;
                        }
                }
                j = n-i;
                addresults(l, r, 2*j);
                if (2*j+1 <= n) {
                        addresults(l, r, 2*j+1);
                }
        }
}

int main()
{
//        int nt;

//        scanf("%d\n", &nt);
//        for(int j = 0; j < nt; ++j) {

//        t.clear();
        scanf("%d\n", &n);
        for(int i = 0; i < n; ++i) {
                int x;

                scanf("%d\n", &x);
                t.push_back(x);
                tpos[x] = i;
        }

        if (n < 3) {
                printf("%d %d\n", 2*n+1, n);
                return 0;
        }

        calc();

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

//        }

        return 0;
}