IOI '05 P4 - Birthday

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minMess(int n, vector<int> &p) {
    vector<int> y(n); // index of value x in p
    for (int i = 0; i < n; ++i) y[p[i]] = i;
    // Binary search on mess
    int left = -1, right = n;
    while (left + 1 < right) {
        int t = (left + right) / 2;
        // See if possible with mess <= t
        vector<int> shiftRange(1+n); // prefix sums
        /* index of shiftRange represents how much to rotate target
        permutation before placing it on initial permutation of 1, 2, .., n */
        for (int x = 0; x < n; ++x) {
            int l = y[x]-x-t, r = y[x]-x+t;
            while (l < 0) l += n;
            while (r < 0) r += n;
            while (l >= n) l -= n;
            while (r >= n) r -= n;
            ++shiftRange[l], --shiftRange[r+1];
            if (r < l) { // split into two ranges [l, n-1] and [0, r]
                ++shiftRange[0], --shiftRange[n];
            }
        }
        bool intersection = false;
        for (int i = 0; i < n; ++i) {
            if (shiftRange[i] == n) intersection = true;
            shiftRange[i+1] += shiftRange[i];
        }

        if (intersection) right = t;
        else left = t;
    }
    return right;
}

int main() {
    int n; cin >> n;
    vector<int> p(n);
    for (int &x : p) cin >> x, --x;
    int a = minMess(n, p);
    reverse(p.begin(), p.end());
    int b = minMess(n, p);
    cout << min(a, b) << endl;
    return 0;
}