<p>You are given an integer array&nbsp;<code>nums</code>. You can choose <strong>exactly one</strong> index (<strong>0-indexed</strong>) and remove the element. Notice that the index of the elements may change after the removal.</p>

<p>For example, if <code>nums = [6,1,7,4,1]</code>:</p>

<ul>
	<li>Choosing to remove index <code>1</code> results in <code>nums = [6,7,4,1]</code>.</li>
	<li>Choosing to remove index <code>2</code> results in <code>nums = [6,1,4,1]</code>.</li>
	<li>Choosing to remove index <code>4</code> results in <code>nums = [6,1,7,4]</code>.</li>
</ul>

<p>An array is <strong>fair</strong> if the sum of the odd-indexed values equals the sum of the even-indexed values.</p>

<p>Return the <em><strong>number</strong> of indices that you could choose such that after the removal, </em><code>nums</code><em> </em><em>is <strong>fair</strong>. </em></p>

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

<pre>
<strong>Input:</strong> nums = [2,1,6,4]
<strong>Output:</strong> 1
<strong>Explanation:</strong>
Remove index 0: [1,6,4] -&gt; Even sum: 1 + 4 = 5. Odd sum: 6. Not fair.
Remove index 1: [2,6,4] -&gt; Even sum: 2 + 4 = 6. Odd sum: 6. Fair.
Remove index 2: [2,1,4] -&gt; Even sum: 2 + 4 = 6. Odd sum: 1. Not fair.
Remove index 3: [2,1,6] -&gt; Even sum: 2 + 6 = 8. Odd sum: 1. Not fair.
There is 1 index that you can remove to make nums fair.
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,1,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong>&nbsp;You can remove any index and the remaining array is fair.
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,2,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong>&nbsp;You cannot make a fair array after removing any index.
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    int waysToMakeFair(vector<int>& nums) {
        int len = nums.size();
        vector<pair<int, int>> mem;
        int count = 0;
        pair<int, int> rest;
        for (int i = 1; i < len; i++ ){
            if (i % 2 == 1) rest.first += nums[i];
            else rest.second += nums[i];
        }
        if (rest.first == rest.second) count++;
        mem.push_back(pair(0, 0));
        for (int i = 1; i < len; i++ ){
            pair<int, int> np = mem[i-1];
            if ( i % 2 == 0 ) {
                np.second += nums[i-1];
                rest.second -= nums[i];
            }
            else {
                np.first += nums[i-1];
                rest.first -= nums[i];
            }
            if (np.first+rest.first == np.second+rest.second) count++;
            mem.push_back(np);
        }
        // for (const pair<int,int>& p : mem) {
        //     cout << p.first << " " << p.second << endl;
        // }
        return count;
    }
};
// 0 0 => 1 6 4 (0) 5 6 {5 6}   2   
// 2 0 => 6 4  (1) 6 6  {6, 4}   1
// 2 1 => 4    (2) 6 1  {4, 0}  6
// 8 1 =>     (3) 8 1  {0, 0}   4


// 5 6 => 4 6 => 4 0 => 

// 0 0 => 1 1 ( 1 1 )
// 1 0 => 1   ( 0 1 )
// 1 1 => ... ( 0 0 )
118300