<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>

int last_less(int node, int l, int r, vector<long long> & seg_tree,long long min_v)
{
    if(seg_tree[node]>min_v)
    return -1;

    if(l==r)
    return l;
    int mid=(l+r)/2;
    if(seg_tree[2*node+2]<=min_v)
    return last_less(2*node+2, mid+1, r, seg_tree, min_v);
    return last_less(2*node+1, l, mid, seg_tree, min_v);

}
void update(int node, int l, int r, vector<long long> & seg_tree, long long val, int ind)
{
    if(l==r)
    seg_tree[node]=val;
    else
    {
        int mid=(l+r)/2;
        if(ind<=mid)
        update(2*node+1, l, mid, seg_tree, val, ind);
        else
        update(2*node+2, mid+1, r, seg_tree, val, ind);
        seg_tree[node]=min(seg_tree[2*node+1], seg_tree[2*node+2]);
    }
}

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n=nums.size();
        vector<long long> seg_tree_min(4*n, LLONG_MAX);
        long long sum=0;
        int ind;
        int ans=INT_MAX;
        for(int i=0; i<n; i++)
        {
            // find last occurance of value less than sum-k
            sum+=nums[i];
            ind=last_less(0, 0, n-1, seg_tree_min, sum-k);
            // cout<<nums[i]<<" "<<ind<<" "<<sum<<" "<<sum-k<<" "<<seg_tree_min[0]<<endl;
            if(ind!=-1)
            ans=min(i-ind, ans);
            else if(sum>=k)
            ans=min(i+1, ans);
            update(0, 0, n-1, seg_tree_min, sum, i);
        }
        if(ans==INT_MAX)
        return -1;
        return ans;

        
    }
};
125100