<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 minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        map<int,int> allsums;  //Count all sums 
        for(int i=0;i<nums.size()/2;i++){
            allsums[nums[i]+nums[n-i-1]]++;
        }
        vector<int> omove(2*limit+2,0),tmove(2*limit+2,0);  //Maximum sum possible is 2*limit and minimum sum = 2
        
        for(int i=0;i<n/2;i++){
            int mis = min(nums[i],nums[n-i-1]) + 1;  // If pair is 2,3 and limit=5 - In one move this pair can acheive sum from 3 to 8
            int mas = max(nums[i],nums[n-i-1]) + limit;  // mis = 3, mas = 8
            omove[mis]++;      // mark omove[3]=1 and 
            omove[mas+1]--;    // omove[9] = -1 
            tmove[mas+1]++;     //Now rest of the range takes 2 moves always no matter what
            tmove[2*limit+1]--; // i.e 2 to 2 and 9 to 10(2*limit)
            tmove[2]++;      // Do the same in tmove
            tmove[mis]--;
        }        
        //Continuing with above ex, omove[3]=1 and omove[9] = -1
        // Cummulative sum will make all elements from 3 to 8 as 1 i.e there is one pair which will make this sum
        // In summary every element of the array will tell how many pairs require one move to get required sum in omove
        // Same in tmove (i.e 2 moves)
        for(int i=1;i<omove.size();i++){
            omove[i]+=omove[i-1];
            tmove[i]+=tmove[i-1];
        }
        // In omove we have to remove sums that have already been acheived i.e in omove we have counted 5 (2+3). Remove that
        for(auto i:allsums){            
            omove[i.first]-=i.second;
        }                
        int mm=INT_MAX;
        // min(Sum of omve and 2*tmove) is answer :)
        for(int i=2;i<omove.size()-1;i++){            
            mm = min(omove[i]+2*tmove[i],mm);
        }
        return mm;
    }
};
119300