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
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int calculate(const vector<int> &A, int l, int r) {
	vector<int> B;
	copy(A.begin()+l, A.begin()+r, back_inserter(B));
	int N = r-l;
	sort(B.begin(), B.end());
	return B[(N-1)/2] + B[N/2];
}

int main() {
	int n;
	cin >> n;
	vector<int> A(n);
	for (auto &a: A) cin >> a;

	int M2 = n+1;
	long long cnt = 0;
	for (int N=n; N>0; N--) {
		int l=0;
		int lt = 0;
		int eq = 0;
		for (int r=0; r<n; r++) {
			if (2*A[r]<M2) lt++;
			if (2*A[r]==M2) eq++;
			while (r-l+1 > N) {
				if (2*A[l]<M2) lt--;
				if (2*A[l]==M2) eq--;
				l++;
			}
			if (r-l+1 == N) {
				if ((lt == N/2 && eq == N%2) && (N%2 == 1 || (calculate(A, l, r+1) == M2))) cnt++;
			}
		}
		M2++;
	}
	cout << 2*n+1 << " " << cnt << "\n";
	return 0;
}