O(n + l): Line Sweep
We are given an array [a_0, ...,  a_{n-1}] of even length such that complementary index pairs (i, j) where i + j = n - 1, must all sum up to the same target val
We are given an array `[a_0, ...,  a_{n-1}]` of even length such that complementary index pairs `(i, j)` where `i + j = n - 1`, must all sum up to the same target value, and we are only allowed to changed values to something in the range `[1, l]` to obtain such.\n\nSo we have two things to determine:\n- What\'s the common target sum which requires the fewest number of values to change?\n- How many values in the array need to change to achieve this target sum?\n\n**LINE SWEEP**\nSuppose we are given a complementary index pair `(i, j)` with values `a_i` and `a_j`, respectively. What do we know?\n- It requires neither value to change to sum to `a_i + a_j`\n- It requires only 1 index to change, in order for this pair to sum up to any value in the range `[min(a_i, a_j) + 1, max(a_i, a_j) + l]`\n- It requires both indexes to change in to sum up to any value for anything outside the above interval\n\nIf by default, we assume that all `n` numbers will need to be changed in order to get to some common target sum `T`, then as we iterate through the pairs of complementary indexes, we know we should correct as follows:\n- if `T = a_i + a_j`, subtract off 2 for pair `(i, j)`\n- if `min(a_i, a_j) + 1 <= T <= max(a_i, a_j)`, subtract off 1 for pair `(i, j)` (with the exception of the prior case that `T = a_i + a_j`, of course)\n\nNow, we don\'t want to loop through each target `T` and then through each possible complementary index pair to get the appropriate number of moves for that target sum value, that will be `O(n * l)`. What we can do is view this as a line sweep problem, where we are tallying the corrections for each possible sum we can form. Define:\n```\ncorrection(T) = # of moves to subtract from naive count n, to achieve common sum T\n```\n\nFor a given complementary index pair `(i,  j)`:\n- `correction(min(a_i, a_j) + 1) += 1`, since we need to change exactly 1 number of `a_i` and `a_j` to make this sum\n- `correction(a_i + a_j) += 1`, since we don\'t need any changes for `(i , j)` to sum up to this value (we will be taking prefix sums later as part of the line sweep, so we\'ve accounted for the other correction at `min(a_i, a_j) + 1`\n- `correction(a_i +  a_j + 1) -= 1`, since we need to change only one of the values `a_i, a_j` to achieve this sum, and we\'re currently at 0 changes from the previous sum\n- `correction(max(a_i, a_j) + l + 1) -= 1`, since now we need to change both values to achieve this sum and beyond\n\n**PREFIX SUM**\nSo now, as we sweep through the possible target sums in ascending order, if we keep track of a prefix sum of `correction` function up to some target `T`, denote it `prefix(T)`, what is it telling us? It\'s telling us, over all possible complementary pairs, how much we need to correct/subtract from the naive assumption that we need to change all `n` numbers to achieve common complementary sum `T`. So our final result will be:\n```\nmin_{T = 2, ..., 2l} n - prefix(T) = n - max_{T=2, ..., 2l} prefix(T)\n```\nwhere it should be clear why `T` ranges between `2` and `2l`.\n\n**CODE**\n```\nclass Solution:\n    def minMoves(self, nums: List[int], limit: int) -> int:\n        n = len(nums)\n        \n        correction_count = defaultdict(int)\n        for i in range(n // 2):\n            l = nums[i]\n            r = nums[n - 1 - i]\n            m = min(l, r)\n            M = max(l, r)\n            correction_count[m + 1] += 1\n            correction_count[l + r] += 1\n            correction_count[l + r + 1] -= 1\n            correction_count[M + limit + 1] -= 1\n        \n        res = float(inf)\n        prefix_sum = 0\n        for s in range(2, 2 * limit + 1):\n            prefix_sum += correction_count[s]\n            res = min(res, n - prefix_sum)\n            \n        return res\n```
[]