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

std::array <int, 1'000'000> val;
std::array <int, 1'000'000> poz;

int main()
{
	int n;
	std::cin >> n;
	std::cout << 2*n + 1 << " ";
	int n1 = n - 1;

	for (int i = 0; i < n; ++i) {
		int a;
		std::cin >> a;
		--a;

		val[i] = a;
		poz[a] = i;
	}

	uint64_t total = 1;
	int l = poz[n1], r = poz[n1];
	int poprz_miotla = 1;
	for (int i = n - 2; i >= 0; --i) {

		//std::cout << "[PRE " << i << "] l/r " << l << "-" << r << " pm " << poprz_miotla
		//	<< " total " << total << std::endl; 

		int p = poz[i];
		if (p < l)
			l = p;
		else if (p > r)
			r = p;

		int curr_przedzial = r - l + 1;

		int max_miotla = 2*(n1 - i) + 1;

 //std::cout << "[MID " << i << "] l/r " << l << "-" << r << " cp " << curr_przedzial << " mm " << max_miotla << std::endl;

		for (int miotla = poprz_miotla + 1; miotla <= max_miotla; ++miotla) {
		//std::cout << "[MIOT " << miotla << "] ";

			if (miotla < curr_przedzial) { //std::cout << "lipper" << std::endl;
				continue; }
			int max_lewa = std::max(0, r - miotla + 1);
			int max_prawa = std::min(n1, l + miotla - 1);
			int tplus = max_prawa - max_lewa - miotla + 2;
			total += tplus;
			//std::cout << max_lewa << "-" << max_prawa << " aka " <<  tplus << " miotel" << std::endl;
			if (miotla == n) {
				i = 0;
		//std::cout << " also spierdalam bo duza miotla xd" << std::endl;
				break;
			}
		}
		poprz_miotla = max_miotla;

		//std::cout << "[POST " << i << "] total " << total << std::endl;
	}

	std::cout << total << std::endl;
}