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
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

int main() {
    int ratingsNum;
    scanf("%d\n", &ratingsNum);

    vector<int> ratingIxs(ratingsNum);

    for (int i = 0; i < ratingsNum; i++) {
        int rating;
        scanf("%d", &rating);
        ratingIxs[rating - 1] = i;
    }

    int hacksNum = 1;
    int leftIx = ratingIxs[ratingsNum - 1];
    int rightIx = ratingIxs[ratingsNum - 1];
    for (int i = ratingsNum - 2; i >= ratingsNum - ratingsNum/2 - 1; i--) {
        int nextIx = ratingIxs[i];
        if (leftIx > nextIx) {
            leftIx = nextIx;
        }
        if (rightIx < nextIx) {
            rightIx = nextIx;
        }

        int range = rightIx - leftIx + 1;
        int highestNum = ratingsNum - i;

        int shorterRange = 2 * highestNum - 2;
        int longerRange = shorterRange + 1;
        if (range < longerRange) {
            int missingToShorter = shorterRange - range;
            hacksNum += max(1, min(min(leftIx, ratingsNum - 1 - rightIx) + 1, missingToShorter));

            if (longerRange <= ratingsNum) {
                int missingToLonger = longerRange - range;
                hacksNum += max(1, min(min(leftIx, ratingsNum - 1 - rightIx) + 1, missingToLonger));
            }
        } else if (range == longerRange) {
            hacksNum++;
        }
    }

    printf("%d %d\n", 2 * ratingsNum + 1, hacksNum);

    return 0;
}