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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cerr << #x << " " << x << endl
#define int long long
#define st first
#define nd second

using namespace std;

const int N(1e6 + 13);
const int MAX(LLONG_MAX);

int n, leftmost, rightmost, seq_len, it, res = 1, smallest, free_tiles, tmp, base_length, leftmoster, righmoster, possible_length;
int arr[N], idx[N];
bool flag;
string s;

int partial_solve() {
  free_tiles = tmp - base_length;
  leftmoster = max((int)1, leftmost - free_tiles);
  righmoster = min(n, rightmost + free_tiles);
  possible_length = righmoster - leftmoster + 1;
  //cout << leftmost << " " << rightmost << " " << free_tiles << " " << leftmoster << " " << righmoster << endl;
  return max((int)0, possible_length - tmp + 1);
}

int32_t main() {
  boost;
  cin >> n;

  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
    idx[arr[i]] = i;
  }

  it = 2;
  leftmost = idx[n];
  rightmost = idx[n];

  while (true) {
    //cout << it << endl;
    smallest = n - it + 1;
    leftmost = min(idx[smallest], leftmost);
    rightmost = max(idx[smallest], rightmost);
    base_length = rightmost - leftmost + 1;

    tmp = 2 * it - 2;
    if (tmp <= n) {
      res += partial_solve();
    } else {
      break;
    }

    tmp = 2 * it - 1;
    if (tmp <= n) {
      res += partial_solve();
    } else {
      break;
    }
    it++;
  }

  cout << 2 * n + 1 << " " << res << endl;
}