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
#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN=1e6+7;
int tab[MAXN];
vector <int> liczby, liczby_pod;

int bs(int szukane) {
    int lewy, prawy, mid;

    lewy = 0;
    prawy = liczby.size()-1;

    while (prawy > lewy) {
        mid = (prawy + lewy) / 2;

        if (liczby[mid] < szukane)
            lewy = mid + 1;

        else
            prawy = mid;
    }

    return lewy;
}

int bs2(int szukane) {
    int lewy, prawy, mid;

    lewy = 0;
    prawy = liczby_pod.size()-1;

    while (prawy > lewy) {
        mid = (prawy + lewy) / 2;

        if (liczby_pod[mid] < szukane)
            lewy = mid + 1;

        else
            prawy = mid;
    }

    return lewy;
}

long long policz(int l, int r) {
    long long wynik;

    wynik = liczby_pod.size();

    if (liczby_pod.size() & 1 == 1)
        wynik += 2 * liczby_pod[(liczby_pod.size() + 1) / 2 - 1];

    else
        wynik += liczby_pod[liczby_pod.size() / 2 - 1] + liczby_pod[liczby_pod.size() / 2];

    return wynik;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, ile_max_wynikow=0, X, Y;
    long long max_wynik=0;

    cin >> n;

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

    for (int i=1; i <= n; i++)
        liczby.push_back(i);

    for (int i=1; i <= n; i++) {
        liczby_pod = liczby;

        for (int j=n; j >= i; j--) {
            if (policz(i, j) == max_wynik)
                ile_max_wynikow++;

            else if (policz(i, j) > max_wynik) {
                max_wynik = policz(i, j);

                ile_max_wynikow = 1;
            }

            liczby_pod.erase(liczby_pod.begin() + bs2(tab[j]));
        }

        liczby.erase(liczby.begin() + bs(tab[i]));
    }

    cout << max_wynik << ' ' << ile_max_wynikow << '\n';

    return 0;
}