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
103
104
105
106
107
108
109
110
111
112
113
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>

using namespace std;


int n;
vector<int> liczby;


void wczytaj() {
    ios_base::sync_with_stdio(false);

    cin >> n;
    liczby.resize(n);

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


void naiwne() {
    int maxCel = 2 * n + 1;
    int wynik = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            vector<int> slice(liczby.begin() + i, liczby.begin() + j);
            sort(slice.begin(), slice.end());
            
            int m = j - i;
            int cel = slice[m / 2] + slice[(m - 1) / 2] + m;

            if (cel == maxCel) {
                // for (int k = i; k < j; k++) cerr << liczby[k] << ' ';
                // for (int l : slice) cerr << l << ' ';
                // cerr << endl;
                wynik ++;
            }
        }
    }

    cout << maxCel << ' ' << wynik << endl;
}

void naiwneLepsze() {
    vector<int> liczba2Idx(liczby.size() + 10);
    set<pair<int, int>> przedzialy;
    int minp, maxp;
    int k;

    for (int i = 0; i < n; i++) {
        liczba2Idx[liczby[i]] = i;
    }

    minp = maxp = liczba2Idx[n];
    k = 1;
    przedzialy.insert({minp, maxp});
    przedzialy.insert({0, n-1});

    for (int i = n-1; i > 0; i--) {
        k ++;
        int idx = liczba2Idx[i];

        int newMinp = min(minp, idx);
        int newMaxp = max(maxp, idx);
        int d = (2*k - 2) - (newMaxp - newMinp);

        if (d >= 0) {            
            int newMincov = max(0, newMinp - d);
            int newMaxcov = min(n-1, newMaxp + d);

            // cerr << i << ": " << newMincov << ": " << newMaxcov << endl;

            for (int span = newMaxp - newMinp; span <= (newMaxp - newMinp) + d; span++) {
                for (int a = newMincov; a <= newMinp; a++) {
                    int b = a + span;
                    if (b >= newMaxp && b <= newMaxcov) {
                        // cerr << "[" << a << " " << b << "] ";
                        przedzialy.insert({a, b});
                    }
                }
            }
        }

        minp = newMinp;
        maxp = newMaxp;

        if (newMinp == 0 && newMaxp == n-1) {
            break;
        }
    }

    // for (auto p : przedzialy) cerr << " (" << p.first << ' ' << p.second << ") ";
    // cerr << endl;

    cout << (2 * n + 1) << ' ' << przedzialy.size() << endl;
}



int main() {
    wczytaj();
    naiwne();
    // naiwneLepsze();

    return 0;
}