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
84
85
86
87
88
89
90
91
92
93
94
95
96
//runda 4C
#include <iostream>

using namespace std;

long wejscie[1000010], n, a;
long long wynik;
long p1St, p1End, p2St, p2End, p2StMax, p2EndMax, nowyZakres, nalewo, naprawo;
//nowyZakres - od p1

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

	cin >> n;
	for(long iN = 0; iN < n; ++iN) {
		cin >> a;
		wejscie[a] = iN;
	}

	wynik = 1LL;
	p1St = wejscie[n];
	p1End = wejscie[n];
	p2St = wejscie[n];
	p2End = wejscie[n];
	//cout << "0:" << wynik << " " << "x" << " " << p1St << " " << p1End << " " << p2St << " " << p2End << " " << nowyZakres << endl;
	for(long s = n - 1; s > 0; --s) {
		nowyZakres = -1;
		//wewnatrz przedzialu
		if(wejscie[s] > p1St && wejscie[s] < p1End) {
			//Sprawdzamy czy jest to warunek graniczny na poprawnosc
			if(2 * n - 2 * s + 1 == p1End - p1St + 1) {
				if((p1St < p2St) || (p1End > p2End))
					++wynik;
				if((p1St == p2St) && (p1End == p2End))
					++wynik;
				if(p1St < p2St)
					p2St = p1St;
				if(p1End > p2End)
					p2End = p1End;
			} else if(2 * n - 2 * s + 1 > p1End - p1St + 1) {
				nowyZakres = (2 * n - 2 * s + 1) - (p1End - p1St + 1);
			}
		//	cout << "1:" << wynik << " " << s << " " << p1St << " " << p1End << " " << p2St << " " << p2End << " " << nowyZakres << endl;
		}  else {
			//na zewnatrz przedzialu
			if(wejscie[s] < p1St)
				p1St = wejscie[s];
			else
				p1End = wejscie[s];
			if(2 * n - 2 * s + 1 >= p1End - p1St + 1) {
				if((p1St < p2St) || (p1End > p2End))
					++wynik;
				if((p1St == p2St) && (p1End == p2End))
					++wynik;
				if(p1St < p2St)
					p2St = p1St;
				if(p1End > p2End)
					p2End = p1End;
				nowyZakres = (2 * n - 2 * s + 1) - (p1End - p1St + 1);
			}
			//cout << "2:" << wynik << " " << s << " " << p1St << " " << p1End << " " << p2St << " " << p2End << " " << nowyZakres << endl;
		}
		if(nowyZakres > 0) {
			p2StMax = p1St - nowyZakres;
			if(p2StMax < 0) p2StMax = 0;
			if(p2StMax >= p2St) p2StMax = p2St;

			p2EndMax = p1End + nowyZakres;
			if(p2EndMax >= n) p2EndMax = n - 1;
			if(p2EndMax <= p2End) p2EndMax = p2End;

			nalewo = p2St - p2StMax + 1;
			naprawo = p2EndMax - p2End + 1;

			wynik += (long long)(((1 + min(nalewo, naprawo)) * min(nalewo, naprawo)) / 2) - 1;
			wynik += (long long)abs(nalewo - naprawo);

			//cout << "3:" << p2StMax << " " << p2EndMax << endl;
			//cout << "3:" << wynik << " " << s << " " << p1St << " " << p1End << " " << p2St << " " << p2End << " " << nowyZakres << endl;


			p2St = p2StMax;
			p2End = p2EndMax;


			//	if((p2St == 0) && (p2End == (n - 1)))
			//	break;
		}

	}

	cout << (long long)n * 2 + 1 << " " << wynik;


	return 0;
}