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
// 2021-4-ran-ranking-sklepow-internetowych.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>

constexpr int MAXN = 1e6 + 7;

long long pos[MAXN];

int main()
{
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	int n, a;
	std::cin >> n;
	for (size_t i = 1; i <= n; i++)
	{
		std::cin >> a;
		pos[a] = i;
	}
	long long answ = 1;
	long long mnpos = pos[n], mxpos = pos[n];
	long long ln = 2;
	for (int i = n - 1; i > 0; i--)
	{
		mnpos = std::min(mnpos, pos[i]);
		mxpos = std::max(mxpos, pos[i]);
		//std::cout << i << '\n';
		//std::cout << mnpos << ' ' << mxpos << ' ' << ln << '\n';
		if (ln <= n && mxpos - mnpos + 1 <= ln)
		{
			
			answ += std::max(1 + std::min(mnpos, n - ln + 1) - std::max(mxpos - ln + 1, 1ll), 0ll);
			//std::cout << 'a' << answ << '\n';
		}
		ln++;
		
		if (ln <= n && mxpos - mnpos + 1 <= ln)
		{
			//std::cout << "!" << ln - mxpos + mnpos << ' ' << mnpos << ' ' << n - mxpos + 1ll << '\n';
			answ += std::max(1 + std::min(mnpos, n - ln + 1) - std::max(mxpos - ln + 1, 1ll), 0ll);
			//answ += std::min(ln - mxpos + mnpos, std::min(mnpos, n - mxpos + 1ll));
			//std::cout << 'b' << answ << '\n';
		}
		ln++;
		//std::cout << '+' << i << ' ' << answ << '\n';
	}
	std::cout << 2 * n + 1 << ' ' << answ << '\n';
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file