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
79
80
81
82
83
#include <stdio.h>
#include <vector>

long long int solution(const std::vector<int> &position, const int n, const int l, const int r, const int top)
{
	if (l == 1 && r == n)
		return 1;
	const auto high = n - top + 1;
	const auto size = r - l + 1;
	if (top <= size / 2)
		return 0;

	auto lsize = l - 1;
	auto rsize = n - r;
	if (position[high - 1] < l)
		lsize = l - position[high - 1] - 1;
	if (r < position[high - 1])
		rsize = position[high - 1] - r - 1;
	const auto msize = std::max(0, top - (size - top) - 1);
	lsize = std::min(lsize, msize);
	rsize = std::min(rsize, msize);
	long long int sum{0};
	const auto min = std::min(lsize, rsize);
	const auto max = std::max(lsize, rsize);
	{
		const auto index = std::min(msize, min - 1) + 1;
		sum += (1 + index) * (index) / 2;
	}
	if (min <= msize)
	{
		const auto count = std::min(msize - min + 1, max - min + 1);
		sum += count * (min + 1);
	}
	if (max < msize)
	{
		const auto a = min;
		const auto b = std::max(1, min + 1 - (msize - max));
		sum += (a + b) * (a - b + 1) / 2;
	}
	return sum;
}

long long int solution(const std::vector<int> &position, const int n)
{
	long long int permutation = 1;
	int top = 1;
	int l = position[n];
	int r = position[n];
	for (int i = n - 1; i >= 1; --i)
	{
		if (position[i] < l || r < position[i])
		{
			const auto p = position[i];
			l = std::min(l, p);
			r = std::max(r, p);
			for (int j = i; j >= 1; --j)
			{
				if (l <= position[j] && position[j] <= r)
					top++;
				else
					break;
			}
			permutation += solution(position, n, l, r, top);
		}
	}
	return permutation;
}

int main()
{
	int n, a;
	std::vector<int> position;

	scanf("%d", &n);
	position.resize(n + 1);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &a);
		position[a] = i;
	}
	printf("%d %lld\n", 2 * n + 1, solution(position, n));
	return 0;
}