Python Hard
\nclass Solution:\n    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:\n        N = len(nums)\n        INF = 10 ** 20\n        pref = [
```\nclass Solution:\n    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:\n        N = len(nums)\n        INF = 10 ** 20\n        pref = [0] + list(accumulate(nums))\n        pref_ind = [0] \n        for i in range(N):\n            pref_ind.append(pref_ind[-1])\n            if nums[i] == 1: pref_ind[-1] += i\n        \n        def go(index):\n            k_copy = k\n            moves = 0\n\n            if nums[index] == 1: k_copy -= 1\n            \n            if k_copy == 0: return moves\n\n            if index > 0 and nums[index - 1]:\n                moves += 1\n                k_copy -= 1\n\n            if k_copy == 0: return moves\n\n            if index < N - 1 and nums[index + 1]:\n                moves += 1\n                k_copy -= 1\n\n            if k_copy == 0: return moves\n\n            delta = min(maxChanges, k_copy)\n\n            k_copy -= delta\n\n            moves += 2 * delta\n\n            if k_copy == 0: return moves\n\n\n            def good(t):\n                # count ones not including index, index + 1, index - 1, within a radius t\n                left_ones = pref[max(index - 1, 0)] - pref[max(0, index - 1 - t)]\n                right_ones = pref[min(N, index + 1 + t + 1)] - pref[min(N, index + 1 + 1)]\n                return left_ones + right_ones >= k_copy\n\n            \n            l, r = 0, N\n\n            while l < r:\n                mid = (l + r) // 2\n\n                if good(mid):\n                    r = mid\n\n                else:\n                    l = mid + 1\n\n            left_close_to_index = max(index - 1, 0)\n            left_far_from_index = max(index - 1 - l, 0)\n            left_count_ones = pref[left_close_to_index] - pref[left_far_from_index]\n\n            right_far_from_index = min(index + l + 2, N)\n            right_close_to_index = min(index + 2, N)\n            right_count_ones = pref[right_far_from_index] - pref[right_close_to_index]\n\n\n            left_index_sum = pref_ind[left_close_to_index] - pref_ind[left_far_from_index]\n            right_index_sum = pref_ind[right_far_from_index] - pref_ind[right_close_to_index]\n\n            moves += index * left_count_ones - left_index_sum\n            moves += right_index_sum - index * right_count_ones\n\n            if left_count_ones + right_count_ones > k_copy:\n                moves -= (l + 1)\n\n            return moves\n        \n\n        best = INF\n        for i in range(N):\n            best = min(best, go(i))\n\n        return best\n```
['Python3']