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

using namespace std;

int main() {
	int n; cin >> n;
	int const funkcja = n + n + 1;

	vector< int > oceny(n);
	for (int i = 0; i < n; ++i) {
		int l; cin >> oceny[i];
	}

	vector< int > indeksy(n);
	iota(indeksy.begin(), indeksy.end(), 0);
	sort(indeksy.begin(), indeksy.end(), [&oceny](int const a, int const b){
		return oceny[a] < oceny[b];
	});

	long long wynik = 0LL;
	int poz_l = 1e9;
	int poz_p = -1;

	for(int szukam = 1; szukam <= n; ++szukam) {
		int potrzebuje = szukam / 2 + 1;

		poz_l = min(poz_l, indeksy[n - potrzebuje]);
		poz_p = max(poz_p, indeksy[n - potrzebuje]);
		int rozm = poz_p - poz_l + 1;

		if (rozm <= szukam) {
			int luz = szukam - rozm;
			int delta = 1 + luz;

			if (int wysieg = poz_l - luz; wysieg < 0) {
				delta -= (-wysieg);
			}
			if (int wysieg = poz_p + luz; n <= wysieg) {
				delta -= (wysieg - n + 1);
			}

			wynik += delta;
		}
	}

	cout << funkcja << " " << wynik << endl;
}