<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the length of the shortest non-empty <strong>subarray</strong> of </em><code>nums</code><em> with a sum of at least </em><code>k</code>. If there is no such <strong>subarray</strong>, return <code>-1</code>.</p>

<p>A <strong>subarray</strong> is a <strong>contiguous</strong> part of an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [1], k = 1
<strong>Output:</strong> 1
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [1,2], k = 4
<strong>Output:</strong> -1
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> nums = [2,-1,2], k = 3
<strong>Output:</strong> 3
</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>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
    static bool cmp(pair<long,int> a, pair<long,int> b) {
        return a.first < b.first;
    }
public:
    int shortestSubarray(vector<int>& nums, int k) {
        
        
        //     2, -1, 2
        
        //  0  2  1  3
        
        //           
        
        // pre[i] - pre[j] >= k
        
        // pre[j] <= pre[i] - k
        
        // when don't conside left anymore?
        // if those are larger
        
        // keep stack increasing
        
        // find cloest element on the left that is smaller than pre[i] - k
        
        // pop while top > pre[i] - k
        
        int length = INT_MAX;
        
        vector<long> pre_sum(nums.size() + 1, 0);
        
        for (int i = 1 ; i < pre_sum.size() ; ++i) {
            pre_sum[i] = pre_sum[i-1] + nums[i-1];
        }
        
        vector<pair<long,int>> index;
        
        for (int i = 0 ; i < pre_sum.size() ; ++i) {
            
            while (!index.empty() && index.back().first >= pre_sum[i]) {
                index.pop_back();
            }
            
            long target = pre_sum[i] - k;
            
            // find right most element that smaller or equal to target
            // target = 5
            auto it = upper_bound(index.begin(), index.end(), pair<long,int>({target, i}), cmp);
            
            if (it != index.begin()) {
                // 0, 1, 2, 3    if it-second = 1, i = 3
                // length = i - it->second
                length = min(length, i - (it-1)->second);
            }
            
            
            index.push_back(pair<long,int>({pre_sum[i], i}));
        }
        
        return length == INT_MAX ? -1 : length;
    }
};
116820