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
#include <bits/stdc++.h>
#define REP(i,n) for (int _n=(n), i=0;i<_n;++i)
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for (int i=(a),_b=(b);i>=_b;--i)
#define TRACE(x) std::cerr << "TRACE(" #x ")" << std::endl;
#define DEBUG(x) std::cerr << #x << " = " << (x) << std::endl;
using std::int64_t;

void init_io() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

int n;
std::vector<int> position;

void read_input() {
  std::cin >> n;
  position.resize(n);
  REP(i,n) {
    int v; std::cin>>v;
    --v;
    position[v] = i;
  }
}

int64_t solve() {
  int64_t ways = 0;
  int alpha = n;
  int beta = 0;
  FOR(cnt, 1, n) {
    const int median = (2*n - cnt - 1)/2;
    alpha = std::min(alpha, position[median]);
    beta = std::max(beta, position[median]);
    const int first_possible_start = std::max(beta - cnt + 1, 0);
    const int last_possible_start = std::min(alpha, n-cnt);
    ways += std::max(last_possible_start - first_possible_start + 1, 0);
  }
  return ways;
}

int main() {
  init_io();
  read_input();
  const int64_t ways = solve();
  std::cout << (2 * n + 1) << " " << ways << "\n";
}