Cyclic Sorting

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5int main(){
    6    ios::sync_with_stdio(0);
    7    cin.tie(0);
    8    int n, q;
    9    cin >> n >> q;
    10    vector<int> vec(n);
    11    for(int i = 0; i < vec.size(); i++){
    12        cin >> vec[i];
    13    }
    14    set<int> decrease;
    15    auto down = [&](int i) {
    16        int nxt = (i + 1) % n;
    17        return vec[i] > vec[nxt];
    18    };
    19    for (int i = 0; i < n; i++) {
    20        if (down(i)) {
    21            decrease.insert(i);
    22        }
    23    }
    24    for(int i = 0; i < q; i++){
    25        int index, x;
    26        cin >> index >> x;
    27        index--;
    28        vec[index] = x;
    29        for(int j = -1; j <= 0; j++){
    30            int pos = (index + j + n) % n;
    31            decrease.erase(pos);
    32            if(down(pos)) decrease.insert(pos);
    33        }
    34        if(decrease.size() > 1){
    35            cout << -1 << '\n';
    36        } else if(decrease.empty()){
    37            cout << 0 << '\n';
    38        } else {
    39            int ans = *decrease.begin();
    40            cout << min(ans + 1, n - ans - 1) << '\n';
    41        }
    42    }
    43    return 0;
    44}