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
#include <iostream>
using namespace std;

int n;
int pos[1000007];

int main()
{
  ios_base::sync_with_stdio(0);

  cin >> n;
  for (int i=0; i<n; i++) {
    int j;
    cin >> j;
    pos[j] = i;
  }

  long long ans = 1;
  int req_start = pos[n];
  int req_end = pos[n];
  int min_req = n;

  for (int length=2; length<n+1; length++) {
    if (length % 2 == 0) {
      min_req--;
      req_start = min(req_start, pos[min_req]);
      req_end = max(req_end, pos[min_req]);
    }
    int min_start = max(0, req_end - length + 1);
    int max_end = min(n-1, req_start + length - 1);
    ans += max(0, max_end - min_start - length + 2);
  }

  cout << 2 * n + 1 << " " << ans;

  return 0;
}