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

using namespace std;


const int MAXN = 1000010;

int pos[MAXN];
int pmax[MAXN];
int pmin[MAXN];

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

  pmax[n] = pos[n];
  pmin[n] = pos[n];

  for (int i = n - 1; i >= 1; i--) {
    pmax[i] = max(pmax[i + 1], pos[i]);
    pmin[i] = min(pmin[i + 1], pos[i]);
  }

  long long int out = 0;
  for (int m = 2 * n; m >= n + 1; m--) {
    int l = pmin[m / 2];
    int r = pmax[m / 2];
    int len = 2 * n + 1 - m;
    int minl = max(1, r - len + 1);
    int maxr = min(n, l + len - 1);
    out += max(0, maxr - minl + 1 - len + 1);
  }

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