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
#include <iostream>
#include <climits>

using namespace std;

void calc(int * arr, int l, int r, bool * exists, int * res) {
    int min = INT_MAX;
    int max = 0;
    int x;
    
    int len = r - l + 1;
    int * tab = new int[len];

    for (int i = l; i <=r; ++i) {
        x = arr[i];
        exists[x] = true;
        min = x < min ? x : min;
        max = x > max ? x : max;
    }
    
    int j = 0;
    for (int i = min; i <= max && j < len; ++i) {
        if (exists[i]) {
            // cerr << "exists " << i << ", put to " << j <<endl;
            tab[j] = i;
            ++j;
        }
    }

    int poz = (len - 1)/2;
    int med_score = len % 2 == 0 ? tab[poz] + tab[poz + 1] : 2 * tab[poz];
    int score = len + med_score;
    // cerr << "l=" << l << ", r=" << r << ", len=" << len << ", poz=" << poz << ", tab[poz]=" << tab[poz] << ", med_score=" << med_score << ", score=" << score << endl;
    // cerr << arr[l] << ',' << arr[r] << ',' << score << endl;
    ++res[score];

    // res[0] - keep max score in this cell
    res[0] = score > res[0] ? score : res[0];

    for (int i = l; i <=r; ++i) {
        exists[arr[i]] = false;
    }

    delete[] tab;
}

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

    int n, x;
    int * tab;
    bool * exists = new bool[1000001];
    int * results = new int[3000001];

    cin >> n;
    tab = new int[n];

    for (int i = 0; i < 1000001; ++i) {
        exists[i] = false;
    }

    for (int i = 0; i < 3000001; ++i) {
        results[i] = 0;
    }

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

    for (int R = 0; R < n; ++R) {
        for (int L = 0; L <= R; ++L){
            calc(tab, L, R, exists, results);
        }
    }

    cout << results[0] << ' ' << results[results[0]];

    return 0;
}