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
#include <cstdio>
#include <vector>

using namespace std;

typedef long long LL;

int main() {
  int n; scanf("%d", &n);
  vector<int> a(n);
  for (int i=0; i<n; ++i) scanf("%d", &a[i]);

  LL res = 0;
  int x = 0, y = n-1;
  for (int i=0; i<n; ++i) {
    int med = (n+1+i)/2;
    while (a[x] < med) ++x;
    while (a[y] < med) --y;
    // fprintf(stderr, "At %d - med %d\n", i, med);
    // fprintf(stderr, "(%d - %d)\n", x, y);
    int add = min(i, x) - max(y - n + i + 1, 0) + 1;
    // fprintf(stderr, "Add %d\n", add);
    if (add > 0) {
      res += add;
    }
  }
  printf("%d %lld\n", n*2 + 1, res);
  return 0;
}