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
 97
 98
 99
100
101
102
// Jan Burdzicki
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 5;

int mediana_w_punkcie(vector <int>& liczby, int L, int R, int ilosc_wartosci, int dlugosc_przedzialu, int dodana_wartosc, int n)
{
	int wynik = 0;

	int ilosc_wszystkich_wartosci = 2 * ilosc_wartosci - 1;
	int ilosc_potrzebnych_mniejszych_wartosci = ilosc_wszystkich_wartosci - dlugosc_przedzialu;

	if(ilosc_potrzebnych_mniejszych_wartosci >= 0)
	{
		int ilosc_mniejszych_L = L - 1;
		int ilosc_mniejszych_R = n - R;

		if(ilosc_mniejszych_L + ilosc_mniejszych_R >= ilosc_potrzebnych_mniejszych_wartosci)
		{
			int do_dodania = min(ilosc_mniejszych_L, ilosc_potrzebnych_mniejszych_wartosci) - ilosc_potrzebnych_mniejszych_wartosci + min(ilosc_mniejszych_R, ilosc_potrzebnych_mniejszych_wartosci) + 1;

			wynik += do_dodania;
		}
	}

	return wynik;
}

int mediana_pomiedzy_punktami(vector <int>& liczby, int L, int R, int ilosc_wartosci, int dlugosc_przedzialu, int dodana_wartosc, int n)
{
	int wynik = 0;

	int ilosc_wszystkich_wartosci = 2 * ilosc_wartosci - 2;
	int ilosc_potrzebnych_mniejszych_wartosci = ilosc_wszystkich_wartosci - dlugosc_przedzialu;

	if(ilosc_potrzebnych_mniejszych_wartosci >= 0)
	{
		int ilosc_mniejszych_L = L - 1;
		int ilosc_mniejszych_R = n - R;

		if(ilosc_mniejszych_L + ilosc_mniejszych_R >= ilosc_potrzebnych_mniejszych_wartosci)
		{
			int do_dodania = min(ilosc_mniejszych_L, ilosc_potrzebnych_mniejszych_wartosci) - ilosc_potrzebnych_mniejszych_wartosci + min(ilosc_mniejszych_R, ilosc_potrzebnych_mniejszych_wartosci) + 1;

			wynik += do_dodania;
		}
	}

	return wynik;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	vector <int> liczby(n + 1);
	vector <int> pozycje_wartosci(n + 1);

	for(int i = 1; i <= n; i++)
	{
		cin >> liczby[i];

		pozycje_wartosci[liczby[i]] = i;
	}

	int L = INF, R = -INF;

	long long ilosc_przedzialow = 0;

	for(int ilosc_wartosci = 1; ilosc_wartosci <= n / 2 + 1; ilosc_wartosci++)
	{
		int dodana_wartosc = n - ilosc_wartosci + 1;

		int pozycja_dodanej_wartosci = pozycje_wartosci[dodana_wartosc];

		L = min(L, pozycja_dodanej_wartosci);
		R = max(R, pozycja_dodanej_wartosci);

		int dlugosc_przedzialu = R - L + 1;

		if((n % 2 == 1) || (n % 2 == 0 && dodana_wartosc > n / 2))
		{
			ilosc_przedzialow += mediana_w_punkcie(liczby, L, R, ilosc_wartosci, dlugosc_przedzialu, dodana_wartosc, n);
		}

		if(((n % 2 == 0) || (n % 2 == 1 && dodana_wartosc > n / 2)) && (dodana_wartosc < n))
		{
			ilosc_przedzialow += mediana_pomiedzy_punktami(liczby, L, R, ilosc_wartosci, dlugosc_przedzialu, dodana_wartosc, n);
		}
	}

	int wynik = 2 * n + 1;

	cout << wynik << " " << ilosc_przedzialow << "\n";
	return 0;
}