C

class Solution {
public:
    vector<int> makeParityAlternating(vector<int>& v) {
        vector<int> a;

        int n = v.size();
        
        for(int j = 0;j < 2;j += 1){
            
            int cur = 0, f = j;
            
            for(int i = 0;i < n;i += 1){
                cur += ((abs(v[i]) & 1) != (f & 1));
                f += 1;
            }

            a.push_back(cur);
        }

        auto get = [&](int par){
            vector<pair<int, int>> vv;

            for(int i = 0;i < n;i += 1){
                bool ok = ((abs(v[i]) & 1) == ((par + i) & 1));

                if(ok){
                    vv.push_back({v[i], i});
                }
                else{
                    vv.push_back({v[i] + 1, i});
                    vv.push_back({v[i] - 1, i});
                }
            }

            sort(vv.begin(), vv.end());

            int ans = 2e9 + 10;
            
            int unique = 0, left = 0;
            vector<int> mp(n);

            for(int i = 0;i < vv.size();i += 1){
                int ind = vv[i].second;

                if(mp[ind] == 0){
                    unique += 1;
                }

                mp[ind] += 1;

                while(unique == n){
                    int range = vv[i].first - vv[left].first;

                    ans = min(ans, range);

                    mp[vv[left].second] -= 1;

                    if(mp[vv[left].second] == 0){
                        --unique;
                    }

                    left += 1;
                }
            }

            return ans;
        };

        int mn = 2e9 + 10;
        
        if(a.front() == min(a.front(), a.back())){
            mn = min(mn, get(0));
        }
        if(a.back() == min(a.front(), a.back())){
            mn = min(mn, get(1));
        }

        return {min(a.front(), a.back()), mn};
    }
};