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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <set>

using namespace std;

int a[1000001];
set<int> ranks;
int n, tmp;

int mediana()
{
	int r_size = ranks.size();

	if (r_size & 1)
	{
		set<int>::iterator el = ranks.begin();
		advance(el, r_size / 2);
		return *el * 2;
	}
	else
	{
		set<int>::iterator el1 = ranks.begin();
		set<int>::iterator el2 = ranks.begin();
		advance(el1, (r_size - 1) / 2);
		advance(el2, (r_size + 1) / 2);
		return *el1 + *el2;
	}
}

int main()
{
	scanf("%d", &n);

	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &a[i]);
		ranks.insert(a[i]);
	}

	int ans, last_removed, max_loss, cnt_smaller, cur_med, last_med;

	ans = 0;
	max_loss = 2 * n + 1;

	for (int l = 0; l < n; ++l)
	{
		cnt_smaller = 0;

		cur_med = mediana();

		if (n - l + cur_med == max_loss) ans++;

		last_med = cur_med;

		last_removed = n;
		for (int r = n - 1; r > l; --r)
		{
			ranks.erase(a[r]);
			last_removed = r;

			cur_med = mediana();
			if (r - l + cur_med == max_loss) ans++;
			
			if (cur_med < last_med) cnt_smaller++;
			else cnt_smaller = 0;
			last_med = cur_med;

			if (cnt_smaller > 150) break;
		}

		for (int i = last_removed; i < n; ++i) ranks.insert(a[i]);

		ranks.erase(a[l]);
	}

	printf("%d %d\n", max_loss, ans);
	return 0;
}