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
#include <iostream>
#include <algorithm>
#ifdef TEST_MODE
#include <fstream>
#endif

using namespace std;

const int kMaxN = 1000000;

int orderedRates[kMaxN];
int sortedIdx[kMaxN + 1];
bool alreadyInRange[kMaxN + 1];

int main() {
    
#ifdef TEST_MODE
    std::ifstream in("1.in"); std::cin.rdbuf(in.rdbuf());
#endif
    std::ios_base::sync_with_stdio(false);
    

    int n;
    cin >> n;
    int coreLeft, coreRight;
    coreLeft = coreRight = -1;
    int minCoreValue = (n+1)/2;
    for ( int i = 0; i < n; ++i ) {
        cin >> orderedRates[i];
        if ( orderedRates[i] >= minCoreValue ) {
            if ( coreLeft < 0 )
                coreLeft = i;
            if (coreRight < i )
                coreRight = i;
        }
        sortedIdx[orderedRates[i]] = i;
    }
    int result = 1;
    for ( int i = n - 1; i > 0; --i ) {
        if ( i % 2 ) {
            minCoreValue = (n + 1 - i)/ 2 + (n+1) / 2;
            while ( orderedRates[coreLeft] < minCoreValue)
                coreLeft++;
            while ( orderedRates[coreRight] < minCoreValue)
                coreRight--;
#ifdef TEST_MODE
            cout << "i: " << i << " coreLeft: " << coreLeft << " coreRight: " << coreRight << " minCoreValue: " << minCoreValue << endl;
#endif
        }
        int l, r;
        l = max(0, coreRight + 1 - i);
        r = min(n - i, coreLeft);
        if ( l <= r)
            result += r - l + 1;
    }
    int targetFunc = 2 * n + 1;
    cout << targetFunc << " " << result << endl;
    return 0;
}