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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Sorter {
	Sorter(const vector<int> &v_) : v(v_) {}
	const vector<int> &v;

	bool operator()(int lhs, int rhs) {
		return v[lhs] < v[rhs];
	}
};

int main() {
	ios_base::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<int> v;
	v.reserve(N);

	vector<int> p;
	p.reserve(N);

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		v.push_back(a);
		p.push_back(i);
	}

	sort(p.begin(), p.end(), Sorter(v));

	long long result = 0;
	int interval_min = N-1;
	int interval_max = 0;
	for (int i = 0; i < N; i++) {
		int g = (i+1)/2;
		int interval_edge1 = p[N-1];
		int interval_edge2 = p[N-1-g];
		interval_min = min(interval_edge1, interval_min);
		interval_min = min(interval_edge2, interval_min);
		interval_max = max(interval_edge1, interval_max);
		interval_max = max(interval_edge2, interval_max);

		int lmin = max(0, interval_max - i);
		int lmax = interval_min;
		int rmin = interval_max;
		int rmax = min(N-1, interval_min + i);

		int res = min(lmax - lmin, rmax - rmin);
		res = min(res, N-i-1);
		if (res >= 0) result += res + 1;
	}

	cout << 2*N+1 << " " << result << endl;

	return 0;
}