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
#include <bits/stdc++.h>

using namespace std;

int position[1000001];

struct intl {
  int beg;
  int end;
} interval;

long long sum(int i, int j) {
    assert(i<=j);
    return (((long long)j)*(j+1))/2 - (((long long)(i-1))*i)/2;
}

long long pick(int x, int y, int z) {
    if(z > x+y) return 0;
    long long result=0;
    if(z==0) {result+=1; ++z; if(z > x+y) return result; }
    result+= sum(z+1,x+y+1)-sum(max(z,x),x+y)-sum(max(z,y),x+y)+
            ((long long)x)*(x+y-max(z,x)+1)+((long long)y)*(x+y-max(z,y)+1);
    return result;
}

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

    for(int i=1; i <= n; ++i) {
        int p;
        scanf("%d",&p);
        position[p]=i;
    }


    int current=n;
    int without_cm1=n-1;
    interval.beg=position[n];
    interval.end=position[n];
    long long ways=0;
    while(current > 1){
        // bez current-1
//        printf("current: %d\n",current);
//        printf("interval=[%d,%d]\n",interval.beg,interval.end);
//        printf("pos[current-1]=%d\n",position[current-1]);
//        printf("without_cm1=%d\n",without_cm1);
        if(position[current-1]<interval.beg) {
//            printf("pick args= %d, %d, %d\n",
//                   interval.beg-position[current-1]-1,n-interval.end,
//                    max(0, without_cm1-position[current-1] ));
            long long waysnow=
              pick(interval.beg-position[current-1]-1,n-interval.end,
                   max(0, without_cm1-position[current-1] ));

//            printf("waysnow= %lld\n",waysnow);
            ways+=waysnow;
            interval.beg=position[current-1];
        }
        else {
            if(position[current-1] > interval.end) {
//                printf("pick args= %d, %d, %d\n",
//                       interval.beg-1,position[current-1]-interval.end-1,
//                        max(0,without_cm1-(n-position[current-1]+1)));
                long long waysnow=
                  pick(interval.beg-1,position[current-1]-interval.end-1,
                      max(0,without_cm1-(n-position[current-1]+1)));


//                printf("waysnow= %lld\n",waysnow);
                ways+=waysnow;
                interval.end=position[current-1];
            }

        }
        without_cm1=max(0,without_cm1-2);
        current--;

    }
    ways+=1;
    printf("%d %lld\n",2*n+1,ways);
    return 0;
}