<p>You are given an integer array <code>nums</code> of <strong>even</strong> length <code>n</code> and an integer <code>limit</code>. In one move, you can replace any integer from <code>nums</code> with another integer between <code>1</code> and <code>limit</code>, inclusive.</p>

<p>The array <code>nums</code> is <strong>complementary</strong> if for all indices <code>i</code> (<strong>0-indexed</strong>), <code>nums[i] + nums[n - 1 - i]</code> equals the same number. For example, the array <code>[1,2,3,4]</code> is complementary because for all indices <code>i</code>, <code>nums[i] + nums[n - 1 - i] = 5</code>.</p>

<p>Return the <em><strong>minimum</strong> number of moves required to make </em><code>nums</code><em> <strong>complementary</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,4,3], limit = 4
<strong>Output:</strong> 1
<strong>Explanation:</strong> In 1 move, you can change nums to [1,2,<u>2</u>,3] (underlined elements are changed).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,2,1], limit = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> In 2 moves, you can change nums to [<u>2</u>,2,2,<u>2</u>]. You cannot change any number to 3 since 3 &gt; limit.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1,2], limit = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> nums is already complementary.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>2 &lt;= n&nbsp;&lt;=&nbsp;10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i]&nbsp;&lt;= limit &lt;=&nbsp;10<sup>5</sup></code></li>
	<li><code>n</code> is even.</li>
</ul>

class Solution {
public:
    int binarySearchMax(vector<int>& v, int value) {
        int left = 0;
        int right = v.size() - 1;
        int mid = -1;
        int an = -1;
        while (left <= right) {
            mid = (left + right) / 2;
            if (v[mid] >= value) {
                right = mid - 1;
            } else {
                an = mid;
                left = mid + 1;
            }
        }
        if (an != -1) {
            return an + 1;
        }
        return 0;
    }

    int binarySearchMin(vector<int>& v, int value) {
        int left = 0;
        int right = v.size() - 1;
        int mid = -1;
        int an = -1;
        while (left <= right) {
            cout << left << " " << right << endl;
            mid = (left + right) / 2;
            if (v[mid] <= value) {
                left = mid + 1;
            } else {
                an = mid;
                right = mid - 1;
            }
        }
        if (an != -1) {
            return v.size() - an;
        }
        return 0;
    }

    int minMoves(vector<int>& nums, int limit) {
        int l = nums.size();
        int vmin[2 * 100000 + 1] = {0};
        int vmax[2 * 100000 + 1] = {0};
        unordered_map<int, int> m;
        for (int i = 0; i < l / 2; i++) {
            int mn = min(nums[i], nums[l - i - 1]);
            int mx = max(nums[i], nums[l - i - 1]);
            int sum = nums[i] + nums[l - i - 1];
            m[sum]++;
            vmax[mx + limit]++;
            vmin[mn + 1]++;
        }
        int mini;
        int maxi;
        for (int i = 1; i <= 2 * limit; i++) {
            if (vmax[i] != 0) {
                maxi = max(maxi, i);
            }
            if (vmin[i] != 0) {
                mini = min(mini, i);
            }
            vmax[i] += vmax[i - 1];
            vmin[i] += vmin[i - 1];
        }
        int ans = INT_MAX;
        for (auto i : m) {
            int curAns = l / 2 - i.second;
            curAns += vmax[i.first-1];
            curAns += vmin[2 * limit] - vmin[i.first];
            // curAns += binarySearchMax(vmax, i.first);
            // curAns += binarySearchMin(vmin, i.first);
            ans = min(ans, curAns);
        }
        if (mini <= maxi) {
            ans = min(ans, l / 2);
        }
        return ans;
    }
};
103800