862

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int ans, sz=A.size();
        deque<int> q;
        int presum[sz+1];
        ans = sz+1;
        presum[0] = A[0];
        for(int i=0; i<sz; i++){
            if(i) presum[i] = presum[i-1] + A[i];
            if(presum[i] >= K) ans = min(ans, i+1);

            while(q.size()>0 && presum[q.front()] + K <= presum[i]){
                ans = min(ans, i-q.front());
                q.pop_front();
            }
            while(q.size()>0 && presum[q.back()] >= presum[i])
                q.pop_back();
            q.push_back(i);
        }
        if(ans == sz+1) ans = -1;
        return ans;
    }
};