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

const int max_n = 1000011;

int n;
int pos[max_n];

int minn(int a, int b) {
  return a < b ? a : b;
}

int maxx(int a, int b) {
  return a > b ? a : b;
}

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

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

  long long cnt = 0;
  int mx = pos[n];
  int mn = pos[n];
  int curr = n;
  for (int len = 1; len <= n; ++len) {
    if (len % 2 == 0) {
      --curr;
      mx = mx < pos[curr] ? pos[curr] : mx;
      mn = mn > pos[curr] ? pos[curr] : mn;     
    }
    // i + len - 1 >= mx && i + len - 1 <= n && i <= mn
    // i >= mx - len + 1 && i <= min(mn, n - len + 1)
    cnt += maxx(minn(mn, n - len + 1) - maxx(1, mx - len + 1) + 1, 0);
  }
  printf("%d %lld\n", 2 * n + 1, cnt);
  return 0;
}