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
#include <cstdio>
#include <algorithm>
#include <cinttypes>
typedef long long ll;
#define MAXN 1000100

int reverse[MAXN];
int N;
int main() {
  scanf("%d", &N);
  int v;
  for (int i = 0; i < N; ++i) {
    scanf("%d", &v);
    reverse[v] = i;
  } 
  ll res = 1;
  int maxpos = reverse[N];
  int minpos = reverse[N];
  int cval = N;
  for (int i = N-1; i > 0; i--) {
    int len = N + 1 - i;
    if ((N - i) & 1) {
      cval -= 1; 
      maxpos = std::max(maxpos, reverse[cval]);
      minpos = std::min(minpos, reverse[cval]);
    }
    int min = std::max(0, maxpos - (len-1)); 
    int max = std::min(N-1, minpos + (len-1));
    res += std::max(max - min - len + 2, 0);
  } 
  printf("%d %" PRId64 "\n", 2 * N + 1, res);
  return 0;
}