<p>You are given an integer array <code>nums</code> and an integer <code>x</code>. In one operation, you can either remove the leftmost or the rightmost element from the array <code>nums</code> and subtract its value from <code>x</code>. Note that this <strong>modifies</strong> the array for future operations.</p>

<p>Return <em>the <strong>minimum number</strong> of operations to reduce </em><code>x</code> <em>to <strong>exactly</strong></em> <code>0</code> <em>if it is possible</em><em>, otherwise, return </em><code>-1</code>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,1,4,2,3], x = 5
<strong>Output:</strong> 2
<strong>Explanation:</strong> The optimal solution is to remove the last two elements to reduce x to zero.
</pre>

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

<pre>
<strong>Input:</strong> nums = [5,6,7,8,9], x = 4
<strong>Output:</strong> -1
</pre>

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

<pre>
<strong>Input:</strong> nums = [3,2,20,1,1,3], x = 10
<strong>Output:</strong> 5
<strong>Explanation:</strong> The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.
</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>
	<li><code>1 &lt;= x &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size();
        unsigned int cnt = UINT_MAX;
        vector<int> lSum;
        vector<int> rSum;

        lSum.push_back(0);
        if (nums[0] <= x) {
            for (int i = 0; i < n; i++) {
                int s = lSum.back() + nums[i];
                if (s <= x) {
                    lSum.emplace_back(s);
                } else {
                    break;
                }
            }
        }
        rSum.push_back(0);
        if (nums[n-1] <= x) {
            rSum.push_back(nums[n-1]);
            for (int i = n-2; i >= 0; i--) {
                int s = rSum.back() + nums[i];
                if (s <= x) {
                    rSum.emplace_back(s);
                } else {
                    break;
                }
            }
        }
        // cout << "n:" << n << " lSize:" << lSum.size() << " rSize:" << rSum.size() << " lLast:" << lSum.back() << " rLast:" << rSum.back() << endl;
        for (int i = 0; i < lSum.size(); i++) {
            auto iter = lower_bound(rSum.begin(), rSum.end(), x-lSum[i]);
            if (iter != rSum.end() && (iter-rSum.begin())+i <= n && lSum[i]+(*iter) == x) {
                cnt = min(cnt, (unsigned int)(i+(iter-rSum.begin())));
                // cout << "  i:" << i << " j:" << (iter-rSum.begin()) << "  l:" << lSum[i] << " r:" << (*iter) << " sum:" << lSum[i]+(*iter) << " cnt:" << cnt << endl;
            }
        }

        return (int)cnt;
    }
};
114375