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
#include<bits/stdc++.h>
using namespace std;
constexpr int MAX_N = 1000007;
int n, t[MAX_N], pos[MAX_N];
struct interval {
  int poc, kon;
};
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 0;i < n;i++){
    cin >> t[i];
    pos[t[i]] = i;
  }
  interval needed = {pos[n], pos[n]};
  auto add_interval = [&](int d) -> int{
    if(needed.kon - needed.poc + 1 > d) return 0;
    int poc = max(needed.kon - d + 1, 0);
    int kon = min(needed.poc + d - 1, n - 1);
    return kon - poc + 2 - d;
  };
  long long res = 0;
  for(int d = 1, med = 2 * n;d <= n;d++, med--){
    if(med & 1){
      int med1 = med >> 1;
      int med2 = med1 + 1;
      needed.poc = min(needed.poc, min(pos[med1], pos[med2]));
      needed.kon = max(needed.kon, max(pos[med1], pos[med2]));
    }
    res += add_interval(d);
    /* cout << "(" << needed.poc << ", " << needed.kon << ") : " << add_interval(d) << '\n'; */
  }

  cout << 2 * n + 1 << ' ' << res << '\n';
}