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

using namespace std;

#define D(x)

vector<int> a,b;


int main() {
    int n,x,v;
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        scanf("%d", &x);
        a.push_back(x);
    }
    b = a;
    reverse(begin(b), end(b));
    for(int i=1;i<n;i++) a[i] = max(a[i-1],a[i]);
    for(int i=1;i<n;i++) b[i] = max(b[i-1],b[i]);
    long ai=0,bi=0, m, r = 1, p, l;

    for(int d=n-1;d>0;d--) {
        m = (2*n+1 - d) /2;
        while(a[ai]<m) ai++;
        while(b[bi]<m) bi++;
        l = (n-d);
        p = min(ai,l)+min(bi,l) - l + 1;
        D(printf("d:%d l:%d m:%d (%d,%d) p: %d\n", d,l , m ,ai, bi, p));
        if (p > 0) r+=p;
    }
    printf("%ld %ld\n",2*n+1,r);
}