Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.
If there is no non-empty subarray with sum at least K, return -1.
 



Example 1:
Input: A = [1], K = 1
Output: 1


Example 2:
Input: A = [1,2], K = 4
Output: -1


Example 3:
Input: A = [2,-1,2], K = 3
Output: 3

 
Note:

1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5
1 <= K <= 10 ^ 9

Difficulty: interview

Starter code:

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        

Solutions:
import collections

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        cum_sum = 0
        queue = collections.deque([(-1, 0)])
        result = len(A) + 1
        for i, v in enumerate(A):
            cum_sum += v    
            if v > 0:
                # find any matches and remove them, since will never have a better match
                while queue and cum_sum - queue[0][1] >= K:
                    e = queue.popleft()
                    #print('remove candidate from start:', e)
                    result = min(result, i - e[0])
            else:
                # for negative numbers pop off any greater cum sums, which will never be a better target
                while queue and cum_sum <= queue[-1][1]:
                    e = queue.pop()
                    #print('remove lesser from end:', e)
        
            queue.append((i, cum_sum))
            #print(queue)            
        return result if result <= len(A) else -1    

# The solution looks good, 
# also: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C%2B%2BJavaPython-O(N)-Using-Deque
class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        queue = collections.deque([(0, -1)])
        prefix_sum = 0
        res = float('inf')
        for i in range(len(A)):
            prefix_sum += A[i]
            while queue and queue[-1][0] > prefix_sum:
                queue.pop()
                
            while queue and prefix_sum - queue[0][0] >= K:
                res = min(res, i - queue[0][1])
                queue.popleft()
            
            queue.append((prefix_sum, i))
        return res if res != float('inf') else -1
        


import collections

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        cum_sum = 0
        queue = collections.deque([(-1, 0)])
        result = len(A) + 1
        for i, v in enumerate(A):
            cum_sum += v    
            # find any matches and remove them, since will never have a better match
            while queue and cum_sum - queue[0][1] >= K:
                e = queue.popleft()
                #print('remove candidate from start:', e)
                result = min(result, i - e[0])
            # pop off any greater cum sums, which will never be a better target
            while queue and cum_sum <= queue[-1][1]:
                e = queue.pop()
                #print('remove greater from end:', e)
        
            queue.append((i, cum_sum))
            #print(queue)            
        return result if result <= len(A) else -1    

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        B = [0]
        
        for a in A:
            B.append(B[-1] + a)
        
        print(B)
        
        dq = collections.deque()
        res = float('inf')
        
        for i, n in enumerate(B):
            
            while dq and B[dq[-1]] >= n:
                dq.pop()
                
            while dq and n - B[dq[0]] >= K:
                res = min(res, i-dq[0])
                dq.popleft()
            
            dq.append(i)
        
        return -1 if res == float('inf') else res


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        total = 0
        q = deque()
        q.append([-1, 0])

        res = float('inf')
        for i, v in enumerate(A):
            total += v
            #print(q[0])
            while q and total - q[0][1] >=K:
                res = min(res, i - q[0][0])
                q.popleft()
                
            while q and total < q[-1][1]:
                q.pop()
                
            q.append([i, total])

        return res if res != float('inf') else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        if not A:
            return -1
        dq = deque([[0, 0]])
        curr_sum = 0
        min_size = len(A) + 1
        for i in range(len(A)):
            curr_sum += A[i]
            while dq and curr_sum - dq[0][1] >= K:
                min_size = min(min_size, i - dq.popleft()[0] + 1)
            while dq and curr_sum <= dq[-1][1]:
                dq.pop()
            dq.append([i+1, curr_sum])
        return min_size if min_size != len(A) + 1 else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        profits = [0]
        for num in A:
            profits.append(profits[-1] + num)
        
        ans = float('inf')
        q = collections.deque()
        for i in range(len(profits)):
            
            py = profits[i]
            while q and py - profits[q[0]] >= K:
                ans = min(ans, i - q[0])
                q.popleft()
            
            while q and py - profits[q[-1]] <= 0:
                q.pop()
            
            q.append(i)
        
        return ans if ans != float('inf') else -1 

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        n = len(A)
        preSum = [0 for i in range(n+1)]
        for i in range(1, n+1):
            preSum[i] = preSum[i-1] + A[i-1]
        # print(preSum)
        deque = []
        i = 0
        ans = n + 1
        while i <= n:
            while deque and preSum[i] - preSum[deque[0]] >= K:
                ans = min(ans, i-deque[0])
                print(ans)
                deque.pop(0)
            while deque and preSum[deque[-1]] >= preSum[i]:
                deque.pop()
            deque.append(i)
            i += 1
            # print(deque)
        return ans if ans < n+1 else -1


from collections import deque

class Solution:
    def shortestSubarray(self, A, K):
        d = collections.deque([[0, 0]])
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i + 1 - d.popleft()[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i + 1, cur])
        return res if res < float('inf') else -1

from collections import deque

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        if not A:
            return -1
        
        sum_A = [0]
        for a in A:
            sum_A.append(a + sum_A[-1])
            
        d = deque()
        res = len(A) + 1
        for i in range(len(sum_A)):
            while d and sum_A[i] <= sum_A[d[-1]]:
                d.pop()
                
            while d and sum_A[i] - sum_A[d[0]] >= K:
                res = min(res, i - d.popleft())
            
            d.append(i)
            
        return res if res != len(A) + 1 else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        L = len(A)
        min_length = L+1
        queue = collections.deque([(0, -1)])
        cursum = 0
        for i in range(L):
            cursum += A[i]
            while queue and cursum-queue[0][0]>=K:
                prevSum, prevIdx = queue.popleft()
                min_length = min(min_length, i-prevIdx)
            while queue and queue[-1][0]>=cursum:
                queue.pop()
            queue.append((cursum,i))
            
        return min_length if min_length<=L else -1
        


class Solution(object):
    def shortestSubarray(self, A, K):
        d = collections.deque([[0, 0]])
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i + 1 - d.popleft()[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i + 1, cur])
        return res if res < float('inf') else -1

class Solution:
    def shortestSubarray(self, A: List[int], k: int) -> int:
        
#         left, right = 0, 0 
#         _sum = 0
#         out = sys.maxsize
#         while right<len(A): 
#             _sum += A[right]
            
#             while left<=right and _sum>=k:
#                 if right-left+1<out: 
#                     out = right-left+1
#                 _sum -= A[left]
#                 left +=1
            
                
#             right +=1
            
#         return out if out!=sys.maxsize else -1

# Fail example
#     [84,-37,32,40,95]
# 167
        prefixSum = [0] 
    
        for i in range(len(A)): 
            prefixSum.append(prefixSum[-1]+A[i])

        q = collections.deque()
        out = sys.maxsize
        
        for i in range(len(prefixSum)): 
            
            while q and prefixSum[i] - prefixSum[q[0]]>=k: 
                out = min(out, i-q.popleft())
            
            while q and prefixSum[i] <= prefixSum[q[-1]]: 
                q.pop()
                
            q.append(i)
            
                
            # q.append(i)
            
        return out if out!=sys.maxsize else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        q = collections.deque()
        n = len(A)
        B = [0] * (n + 1)
        for i in range(n):
            B[i+1] = A[i] + B[i]
        
        res = float('inf')
        for i in range(n + 1):
            while q and B[i] < B[q[-1]]:   # maintain increasing Manatonic queue
                q.pop()
            
            while q and B[i] - B[q[0]] >= K:   # find the nearest previous element with sum at least K
                res = min(res, i - q.popleft())
            
            q.append(i)
        
        return res if res != float('inf') else -1

from typing import List
import heapq
import math

class Solution:
    def shortestSubarray(self, A: List[int], k: int) -> int:
        shortest = math.inf 
        sum = 0
        #priority queue to store tuples (partial_sum, index_last_element)
        pq = []
        #we iterate over array
        for counter, value in enumerate(A):
            sum += value
            if sum >= k:
                shortest = counter + 1 if counter < shortest else shortest
            
            while pq and sum - pq[0][0] >= k:
                shortest = counter - pq[0][1] if counter - pq[0][1] < shortest else shortest
                heapq.heappop(pq)  
                            
            heapq.heappush(pq, (sum, counter))
            
        return shortest if shortest != math.inf else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        sm = 0
        pref = []
        mn = sys.maxsize

        for i in range(len(A)):
            pref.append(A[i] + sm)
            sm += A[i]
        
        st = [(0, -1)]
        
        for i in range(len(A)):
            while len(st) and pref[i] < st[-1][0] :
                st.pop()
                
            while len(st) and pref[i] - st[0][0] >= K:
                mn = min(mn, i - st[0][1])
                st.pop(0)
                
            st.append([pref[i], i])
            
        return mn if mn != sys.maxsize else -1
                
            
                
            


class Solution:
    def shortestSubarray(self, A: List[int], k: int) -> int:
        # d = collections.deque([[0, 0]])
        # res, cur = float('inf'), 0
        # for i, a in enumerate(A):
        #     cur += a
        #     while d and cur - d[0][1] >= K:
        #         res = min(res, i + 1 - d.popleft()[0])
        #     while d and cur <= d[-1][1]:
        #         d.pop()
        #     d.append([i + 1, cur])
        # return res if res < float('inf') else -1
        
        d = collections.deque([[0,0]])
        cur = 0
        res = float('inf')
        
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= k:
                l = d.popleft()[0]
                res = min(res, i - (l-1))
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i+1, cur])
        return res if res < float('inf') else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        presum = [0]
        for x in A: 
            if x>=K: return 1
            presum.append(presum[-1]+x)
        
        q = collections.deque()
        ans = math.inf
        for i, x in enumerate(A):
            while q and presum[i+1]-presum[q[-1]]<=x: q.pop()
            q.append(i)
            while q and (presum[i+1]-presum[q[0]]>=K or i+1-q[0]>=ans):
                ans = min(ans, i+1-q[0])
                q.popleft()
        return ans if ans!=math.inf else -1
            
        


from typing import List



class Solution:
    def shortestSubarray(self, arr: List[int], K: int) -> int:
        pr_arr = [arr[i] for i in range(len(arr))]
        for i in range(1, len(arr)):
            pr_arr[i] = pr_arr[i - 1] + arr[i]

        q = []
        q.append((0, -1))
        min_window_size = float('inf')
        for i, val in enumerate(pr_arr):
            while len(q) > 0 and q[len(q) - 1][0] >= val:
                q.pop()

            q.append((val, i))

            window_sum = val - q[0][0]
            while window_sum >= K:
                min_window_size = min(min_window_size, i - q[0][1])
                q.pop(0)

                if len(q) == 0:
                    break

                window_sum = val - q[0][0]

        if min_window_size == float('inf'):
            return -1
        return min_window_size

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        pref = [0] + [*accumulate(A)]
        
        ans = math.inf
        q = deque()
        for i, s in enumerate(pref):
            while q and pref[q[-1]] >= s:
                q.pop()
            
            while q and s - pref[q[0]] >= K:
                ans = min(i - q[0], ans)
                q.popleft()
            
            q.append(i)
        
        return -1 if ans == math.inf else ans
        
        # keep smallest prefix sum
        # current sum - smallest prefix sum >= K
        # record smallest length
        # pop it out
        
        # 2, 5, 6
        # 6
        # 8


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        return shortest_subarray(A, K)

def shortest_subarray(A: List[int], K: int) -> int:
    n = len(A)
    sums = [0] * (n + 1)
    for i in range(n):
        sums[i+1] = sums[i] + A[i]
    result = n + 1
    q = deque()
    for i, total in enumerate(sums):
        while q and total < sums[q[-1]]:
            q.pop()
        while q and total - sums[q[0]] >= K:
            result = min(result, i - q.popleft())
        q.append(i)
    return result if result <= n else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        
        n = len(A)
        
    
        if n == 1:
            return  -1 if A[0]<K else 1
        
        if any(A) >= K:
            return 1
        
        s = [0]
        
        
        for i in range(n):
            
            s.append(s[-1]+A[i])
            
            
            
            
        print(s)    
        i = 0
        
        deque = []
        min_length = n+1
        while i<n+1:
            
            #print(deque)

            while len(deque) > 0 and s[deque[-1]]>=s[i]:
                
                deque.pop()
                
               
            while len(deque) > 0 and s[i]-s[deque[0]]>=K:
                k = deque.pop(0)
                
                min_length = min(min_length, i - k)
            
            deque.append(i)
            i+=1
        return min_length if min_length<n+1 else -1
            
                
                
        
                
                
                
                


from collections import deque
class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        if not len(A):
            return -1
        A += [0]
        prefsum = [0]
        for n in A:
            prefsum.append(prefsum[-1] + n)
        ans = len(A) + 1
        deq = deque()
        for i in range(len(A)):
            while len(deq) and prefsum[i] - prefsum[deq[0]] >= K:
                ans = min(i - deq[0], ans)
                deq.popleft()
            while len(deq) and prefsum[i] <= prefsum[deq[-1]]:
                deq.pop()
            deq.append(i)
        if ans == len(A) + 1:
            return -1
        return ans

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        l= 0 
        summ = 0
        A.insert(0,0)
        ln = len(A)
        for i in range(1,ln):
            A[i]+=A[i-1]
        minq = collections.deque([0])
        best = float('inf')
        for r in range(1,ln):
            while minq and A[r]-A[minq[0]]>=K:
                best = min(best,r-minq[0])
                minq.popleft()
            while minq and A[minq[-1]]>A[r]:
                minq.pop()
            minq.append(r)
        return best if best!=float('inf') else -1

from collections import deque
class Solution:
    def shortestSubarray(self, A, K):
        acc = [0]
        for v in A:
            acc.append(acc[-1] + v)
        ans, monoq = float('inf'), deque()
        for size, curS in enumerate(acc):
            while monoq and curS < acc[monoq[-1]]:
                monoq.pop()
            while monoq and curS - acc[monoq[0]] >= K:
                ans = min(ans, size - monoq.popleft())
            monoq.append(size)
        return ans if ans != float('inf') else -1


import collections
class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        n = len(A)
        p = [0]
        
        for x in A:
            p.append(p[-1] + x)
            
        # print(p)
        
        ans = n+1
        q = collections.deque()
        
        for key,val in enumerate(p):
            while q and val <= p[q[-1]]:
                q.pop()
            
            while q and val - p[q[0]] >= K:
                ans = min(ans, key - q.popleft())
                
            q.append(key)
            # print(q)
            
        return ans if ans < n+1 else -1
        
        
        
            
                
            


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        s = [0]
        
        for x in A: 
            s += s[-1] +x, 
      
        q = []
        res = len(A) + 2
        
        for i, val in enumerate(s): 
            
            while q and val - q[0][0] >= K:
                res = min(res, i - heapq.heappop(q)[1]) 
            
            heapq.heappush(q, (val, i))
            
        return res if res < len(A) + 2 else -1 

            
        


from collections import deque

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        d = deque([(0,0)])
        curr = 0
        n = len(A)
        res = n + 1
        
        for r in range(n):
            curr += A[r]

            while d and curr - d[0][1] >= K:
                res = min(res, r - d.popleft()[0] + 1)
            while d and curr <= d[-1][1]:
                d.pop()
            d.append((r + 1, curr))

        return res if res != n + 1 else -1
        


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        if max(A) >= K:
            return 1
        n = len(A)
        prefix = [0] * (n+1)
        for i in range(1, n+1):
            prefix[i] = prefix[i-1] + A[i-1]
        res = n+1
        dq = deque()
        for y, py in enumerate(prefix):
            while dq and prefix[dq[-1]] > py:
                dq.pop()
            while dq and py - prefix[dq[0]] >= K:
                res = min(res, y-dq.popleft())
            dq.append(y)
        return res if res <= n else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        d = collections.deque([[0, 0]])
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i + 1 - d.popleft()[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i + 1, cur])
        return res if res < float('inf') else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
       
        N = len(A)
        P = [0]
        for x in A:
            P.append(P[-1] + x)

        #Want smallest y-x with Py - Px >= K
        ans = N+1 # N+1 is impossible
        monoq = collections.deque() #opt(y) candidates, represented as indices of P
        for y, Py in enumerate(P):
            #Want opt(y) = largest x with Px <= Py - K
            while monoq and Py <= P[monoq[-1]]:
                monoq.pop()

            while monoq and Py - P[monoq[0]] >= K:
                ans = min(ans, y - monoq.popleft())

            monoq.append(y)

        return ans if ans < N+1 else -1

class Solution:
    def shortestSubarray(self, arr, k):
        n = len(arr)
        
        # build prefix sums
        pSums = [0]
        for x in arr:
            pSums.append(pSums[-1] + x)
            
        res = n + 1
        q = deque()
        
        for y, Py in enumerate(pSums):
            while q and Py <= pSums[q[-1]]:
                q.pop()
                
            while q and Py - pSums[q[0]] >= k:
                res = min(res, y - q.popleft())

            q.append(y)
            
        return res if res < n + 1 else -1
        
            


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        queue = [[0,0]]
        x = 0
        ans = float('inf')
        for index, val in enumerate(A):
            x += val
            while queue and x - queue[0][1] >= K:
                ans = min(ans, index+1-queue[0][0])
                queue.pop(0)
            while queue and x <= queue[-1][1]:
                queue.pop()
            queue.append([index+1, x])
        if ans == float('inf'):
            return -1
        return ans


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        pref = [0] + list(itertools.accumulate(A))
        
        q = deque()
        
        ans = math.inf
        for i, n in enumerate(pref):
            while q and pref[q[-1]] > n:
                q.pop()
                
            while q and n - pref[q[0]] >= K:
                ans = min(ans, i - q.popleft())
            
            q.append(i)
        
        return -1 if ans == math.inf else ans

class Solution(object):
    def shortestSubarray(self, A, K):
        N = len(A)
        P = [0]
        for x in A:
            P.append(P[-1] + x)

        #Want smallest y-x with Py - Px >= K
        ans = N+1 # N+1 is impossible
        monoq = collections.deque() #opt(y) candidates, represented as indices of P
        for y, Py in enumerate(P):
            #Want opt(y) = largest x with Px <= Py - K
            while monoq and Py <= P[monoq[-1]]:
                monoq.pop()

            while monoq and Py - P[monoq[0]] >= K:
                ans = min(ans, y - monoq.popleft())

            monoq.append(y)

        return ans if ans < N+1 else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        S = [0]
        res = float('inf')
        for num in A:
            S.append(S[-1]+num)
        q = []
        for i, s in enumerate(S):
            while q and S[q[-1]] >= s:
                q.pop()
            while q and S[q[0]] + K <= s:
                cur_i = q.pop(0)
                res = min(res, i-cur_i)
            q.append(i)
        if res == float('inf'):
            return -1
        else:
            return res
        # n = len(A)
        # dp = [[0]*n for _ in range(n)]
        # res = float('inf')
        # for i in range(len(A)):
        #     if i == 0:
        #         dp[0][i] = A[i]
        #     else:
        #         dp[0][i] = dp[0][i-1] + A[i]
        #     if dp[0][i] >= K:
        #         res = min(res, i+1)
        # for i in range(1,n):
        #     for j in range(i,n):
        #         dp[i][j] = dp[i-1][j] - A[i-1]
        #         if dp[i][j] >= K:
        #             res = min(res, j-i+1)
        # if res == float('inf'):
        #     return -1
        # return res


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        # Sliding window approach with prefix sums and monotonic queue
        prefix_sums = [0]
        prefix_sum = 0
        for a in A:
            prefix_sum += a
            prefix_sums.append(prefix_sum)
            
        # Monotonic queue to hold increasing indices
        from collections import deque
        mono_q = deque()
        min_len = len(A) + 1
        
        # Sliding window        
        for y, Py in enumerate(prefix_sums):
            # Pop the indices that will break the monotonically increasing characteristic 
            # from the right
            while mono_q and Py <= prefix_sums[mono_q[-1]]:
                mono_q.pop()
            
            while mono_q and Py - prefix_sums[mono_q[0]] >= K:
                min_len = min(y - mono_q.popleft(), min_len)
            
            mono_q.append(y)                        
        return min_len if min_len < len(A) + 1 else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        s = [0]
        
        for x in A:
            s += s[-1] + x, 
        
        stack = []
        res = len(s) + 1
        
        for i, x in enumerate(s):
            
            while stack and x <= s[stack[-1]]:
                stack.pop()
            
            while stack and x - s[stack[0]] >=K:
                res = min(res, i - stack.pop(0))
            
            stack += i,
        
        return res if res < len(s) + 1 else -1 
        
        


from bisect import bisect_left
from itertools import accumulate

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        MAX_L = 10**9
        res = Solver(A, K, MAX_L).solve(0, len(A)-1)
        return res if res < MAX_L else -1
        
class Solver:
    def __init__(self, A, K, MAX_L):
        self.A = A
        self.K = K
        self.MAX_L = MAX_L
        
    def solve(self, i, j):
        if i == j:
            return 1 if self.A[i] >= self.K else self.MAX_L
        
        if sum((abs(self.A[v]) for v in range(i, j+1))) < self.K:
            return self.MAX_L
        
        m = (i + j) // 2
        return min(self.solve(i,m), self.solve(m+1,j), self.solve_pivot(i,j,m))
    
    def bin_search(self, arr, val, v):   
        if arr[-1] < v:
            return self.MAX_L
        
        return val[bisect_left(arr, v)]
    
    def solve_pivot(self, i, j, m):
        leftv, leftc = self.min_arr(m, i-1, -1)
        rightv, rightc = self.min_arr(m+1, j+1, 1)
        ans = self.MAX_L
        
        for li in range(len(leftv)):
            l_v,l_cnt = leftv[li], leftc[li]
            r_cnt = self.bin_search(rightv, rightc, self.K-l_v)
            ans = min(ans, l_cnt + r_cnt)
        
        return ans
         
    def min_arr(self, start, stop, step):
        resv, resc = [], []
        acc = 0
        for i in range(start, stop, step):
            acc += self.A[i]
            if (not resv) or acc > resv[-1]:
                resv.append(acc)
                resc.append(abs(start-i)+1)
        return resv, resc

from collections import deque

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        q = deque([(0, 0)])
        presum, ans = 0, float('inf')
        for idx, n in enumerate(A):
            presum += n
            while q and presum - q[0][1] >= K:
                ans = min(ans, idx + 1 - q.popleft()[0])
            while q and q[-1][1] >= presum: q.pop()
            q.append((idx + 1, presum))
        
        return ans if ans < float('inf') else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        psum = 0
        total = 0
        dq = deque([(0,-1)])
        res = float('inf')
        for i, a in enumerate(A):
            psum += a
            # print(dq, i, a, psum)
            while dq and dq[-1][0]>psum:
                dq.pop()
            
            while dq and psum-dq[0][0]>=K:
                res = min(res, i-dq.popleft()[1])
            #  print(dq, res)  
            dq.append((psum, i))
        #print(dq)
        return res if res!=float('inf') else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        N = len(A)
        P = [0]
        for x in A:
            P.append(P[-1] + x)  #append the current sum +=x
            
        ans = N + 1 
        monoq = collections.deque()
        for y, Py in enumerate(P):
            while monoq and Py < P[monoq[-1]]:
                monoq.pop()
                
            while monoq and Py - P[monoq[0]] >=K:
                ans = min(ans, y-monoq.popleft())
            monoq.append(y)
        if ans < N+1:
            
            return ans
        else:
            return -1 
        
        
        
        
        # if not A:
        #     return -1 
        # sum = 0 
        # for i in range(len(A)):
        #     sum += A[i] 
        #     if sum < K:
        #         i +=1 
        #     elif sum > K:
        #         i -=1 
        #     else:
        #         return i+1 
        # return -1 


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        pre = [0]
        n = len(A)
        for num in A:
            pre.append(num + pre[-1])
            
        ans = n + 1
        stack = deque() # indices of possible start positions
        for i in range(n + 1):
            while stack and pre[i] - pre[stack[0]] >= K:
                ans = min(ans, i - stack.popleft())
            
            while stack and pre[i] <= pre[stack[-1]]:
                stack.pop()
            stack.append(i)
            
        return ans if ans <= n else -1
    


class Solution:
    def shortestSubarray(self, nums: List[int], K: int) -> int:
        possible_lefts = deque([(0,-1)])
        shortest = float('inf')
        
        total = 0
        
        for right, num in enumerate(nums):
            total += num
            
            while possible_lefts and total-possible_lefts[0][0] >= K:
                shortest = min(shortest, right-possible_lefts.popleft()[1])
            
            while possible_lefts and possible_lefts[-1][0] > total:
                possible_lefts.pop()
            
            possible_lefts.append((total, right))
        
        
        return shortest if shortest != float('inf') else -1
        


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        # (index, value)
        queue = collections.deque([[0, 0]])
        res = float('inf')
        
        curr = 0
        for i, a in enumerate(A):
            curr += a
            while queue and curr - queue[0][1] >= K:
                tmp = queue.popleft()
                res = min(res, i - tmp[0] + 1)
            while queue and curr < queue[-1][1]:
                queue.pop()
            queue.append([i+1, curr])
        
        return res if res != float('inf') else -1


from bisect import bisect_left
from itertools import accumulate

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        MAX_L = 10**9
        res = Solver(A, K, MAX_L).solve(0, len(A)-1)
        return res if res < MAX_L else -1
        
class Solver:
    def __init__(self, A, K, MAX_L):
        self.A = A
        self.K = K
        self.MAX_L = MAX_L
        
    def solve(self, i, j):
        if i == j:
            return 1 if self.A[i] >= self.K else self.MAX_L
        
        if sum((abs(self.A[v]) for v in range(i, j+1))) < self.K:
            return self.MAX_L
        
        m = (i + j) // 2
        return min([self.solve(i,m), self.solve(m+1,j), self.solve_pivot(i,j,m)])
    
    def bin_search(self, arr, v):   
        if arr[-1][0] < v:
            return self.MAX_L
        
        i = bisect_left(arr, (v, 0))
        return arr[i][1]
    
    def solve_pivot(self, i, j, m):
        left = self.min_arr(m, i-1, -1)
        right = self.min_arr(m+1, j+1, 1)
        ans = self.MAX_L
        
        for l_v, l_cnt in left:
            r_cnt = self.bin_search(right, self.K-l_v)
            ans = min(ans, l_cnt + r_cnt)
        
        return ans
         
    def min_arr(self, start, stop, step):
        res = []
        acc = 0
        for i in range(start, stop, step):
            acc += self.A[i]
            if (not res) or acc > res[-1][0]:
                res.append((acc, abs(start-i)+1))
        return res

from queue import deque
class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        sums=[0]
        for i in A:
            sums.append(sums[-1]+i)
        
        min_l=len(A)+1
        q=deque([])
        
        for i in range(len(sums)):
            while q and sums[q[-1]]>=sums[i]:
                q.pop()
            while q and sums[i]-sums[q[0]]>=K:
                min_l=min(min_l,i-q.popleft())
                
            q.append(i)
        
        if min_l>len(A): return -1
        else: return min_l


import collections

class Solution:
    def shortestSubarray(self, A, K):
        d = collections.deque()
        cummulative_sum = [0]
        
        for a in A:
            cummulative_sum.append(cummulative_sum[-1] + a)
        
        ans = len(cummulative_sum)

        for idx, x in enumerate(cummulative_sum):
            while d and x <= cummulative_sum[d[-1]]:
                d.pop()
            
            while d and x - cummulative_sum[d[0]] >= K:
                ans = min(ans, idx - d[0])
                d.popleft()
            
            d.append(idx)
        
        return ans if ans != len(cummulative_sum) else -1

from heapq import *
class Solution:
    def shortestSubarray(self, A, K):
        heap, curS, ans = [(0, -1)], 0, float('inf')
        for i, v in enumerate(A):
            curS += v
            while heap and curS - heap[0][0] >= K:
                ans = min(ans, i - heappop(heap)[1])
            heappush(heap, (curS, i))
        return ans if ans != float('inf') else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        prefix = [0] * (len(A)+1)
        for i in range(len(A)):
            prefix[i+1] = prefix[i] + A[i]
            
        monoq = deque()
        ans = len(prefix)
        for i, p in enumerate(prefix):
            while monoq and prefix[monoq[-1]]>=p:
                monoq.pop()
            while monoq and p - prefix[monoq[0]]>=K:
                ans = min(ans, i-monoq.popleft())
            monoq.append(i)
            
        return ans if ans<len(prefix) else -1

from bisect import bisect_left
from itertools import accumulate

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        MAX_L = 10**9
        res = Solver(A, K, MAX_L).solve(0, len(A)-1)
        return res if res < MAX_L else -1
        
class Solver:
    def __init__(self, A, K, MAX_L):
        self.A = A
        self.K = K
        self.MAX_L = MAX_L
        
    def solve(self, i, j):
        if i == j:
            return 1 if self.A[i] >= self.K else self.MAX_L
        
        if sum((abs(self.A[v]) for v in range(i, j+1))) < self.K:
            return self.MAX_L
        
        m = (i + j) // 2
        return min(self.solve(i,m), self.solve(m+1,j), self.solve_pivot(i,j,m))
    
    def bin_search(self, arr, v):   
        if arr[-1][0] < v:
            return self.MAX_L
        
        i = bisect_left(arr, (v, 0))
        return arr[i][1]
    
    def solve_pivot(self, i, j, m):
        left = self.min_arr(m, i-1, -1)
        right = self.min_arr(m+1, j+1, 1)
        ans = self.MAX_L
        
        for l_v, l_cnt in left:
            r_cnt = self.bin_search(right, self.K-l_v)
            ans = min(ans, l_cnt + r_cnt)
        
        return ans
         
    def min_arr(self, start, stop, step):
        res = []
        acc = 0
        for i in range(start, stop, step):
            acc += self.A[i]
            if (not res) or acc > res[-1][0]:
                res.append((acc, abs(start-i)+1))
        return res

import bisect

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        n = len(A)
        preSums = [0] * (n + 1)
        for i in range(n): 
            preSums[i + 1] = preSums[i] + A[i]
            
        dque = collections.deque()
        shortest = n + 1
        for i in range(n + 1):
            while dque and preSums[i] - preSums[dque[0]] >= K: 
                shortest = min(shortest, i - dque.popleft())
            while dque and preSums[i] <= preSums[dque[-1]]: 
                dque.pop()
            dque.append(i)
        return shortest if shortest <= n else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        presum = [0]
        for x in A: 
            # if x>=K: return 1, faster without this one
            presum.append(presum[-1]+x)
        
        q = collections.deque()
        ans = math.inf
        for i, x in enumerate(A):
            while q and presum[i+1]-presum[q[-1]]<=x: q.pop()
            q.append(i)
            while q and (presum[i+1]-presum[q[0]]>=K):# or i+1-q[0]>=ans:
                ans = min(ans, i+1-q[0])
                q.popleft()
        return ans if ans!=math.inf else -1
            
        


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        # make p array which is a cumulative sum
        p=[0]
        
        for i in range(len(A)):
            p.append(p[-1]+A[i])
            
        q=[]
        result=len(A)+1 # a high value
        for i in range(len(A)+1):
            
            while(q and p[i]-p[q[0]]>=K):
                result = min( result , i-q[0])
                q.pop(0)
                
            while(q and p[i]-p[q[-1]]<=0):
                q.pop()
            
            q.append(i)
            
        return(-1 if result==len(A)+1 else result)
            


import collections
class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        suma = [0]
        
        for item in A:
            suma.append(suma[-1] + item)
            
            
        ansr = len(A) + 1
        
        queue = collections.deque()
        
        for i in range( len(suma)):
           
            while queue and suma[i] - suma[queue[0]] >= K:
                ansr = min(ansr, i-queue[0])
                queue.popleft()
            
            #shrink the window from left
            while queue and suma[i] <= suma[queue[-1]]:
                queue.pop()
                
            queue.append(i)
            
        
        if ansr == len(A) + 1:
            return -1
        else:
            return ansr


from collections import deque

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        rs = [0]
        for n in A: rs.append(rs[-1]+n)
        print(rs)
        q = deque()
        mn = float('inf')
        for i,s in enumerate(rs):
            while q and s <= rs[q[-1]]:
                q.pop()
            while q and s-rs[q[0]] >= K:
                mn = min(mn,i-q.popleft())
            q.append(i)
        return mn if mn != float('inf') else -1

import collections

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        if not A:
            return -1
        
        if len(A) == 1:
            if A[0] >= K:
                return 1
            return -1
        
        increasing_A = [0]
        for i in A:
            increasing_A.append(increasing_A[-1]+i)
            
        min_length = float('inf')
        queue = collections.deque()
        
        for i,v in enumerate(increasing_A):
            while queue and v <= increasing_A[queue[-1]]:
                queue.pop()
                
            while queue and v-increasing_A[queue[0]] >= K:
                min_length = min(min_length, i-queue.popleft())
            
            queue.append(i)
            
        if min_length == float('inf'):
            return -1
        return min_length

class Solution(object):
    def shortestSubarray(self, A, K):
        N = len(A)
        P = [0]
        for x in A:
            P.append(P[-1] + x)

        #Want smallest y-x with Py - Px >= K
        ans = N+1 # N+1 is impossible
        monoq = collections.deque() #opt(y) candidates, represented as indices of P
        for y, Py in enumerate(P):
            #Want opt(y) = largest x with Px <= Py - K
            while monoq and Py <= P[monoq[-1]]:
                monoq.pop()

            while monoq and Py - P[monoq[0]] >= K:
                ans = min(ans, y - monoq.popleft())

            monoq.append(y)

        return ans if ans < N+1 else -1
                
        
                
        
        
            
        
            


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        
        preSum = [0]
        for e in A:
            preSum.append(preSum[-1] + e)
        
        min_len = sys.maxsize
        
        
        #0 2 1 3 7 
        
        #0 1 3 7
        
        q = collections.deque([])
        for i in range(len(preSum)):
            while q and preSum[q[-1]] > preSum[i]:
                q.pop()
            while q and preSum[i] - K >= preSum[q[0]]:
                min_len = min(min_len, i-q.popleft())       

            q.append(i)
        
        return min_len if min_len != sys.maxsize else -1


# Prepare
# From @Sarmon:
# \"What makes this problem hard is that we have negative values.
# If you haven't already done the problem with positive integers only,
# I highly recommend solving it first\"

# Minimum Size Subarray Sum

# Explanation
# Calculate prefix sum B of list A.
# B[j] - B[i] represents the sum of subarray A[i] ~ A[j-1]
# Deque d will keep indexes of increasing B[i].
# For every B[i], we will compare B[i] - B[d[0]] with K.


# Complexity:
# Every index will be pushed exactly once.
# Every index will be popped at most once.

# Time O(N)
# Space O(N)


# How to think of such solutions?
# Basic idea, for array starting at every A[i], find the shortest one with sum at leat K.
# In my solution, for B[i], find the smallest j that B[j] - B[i] >= K.
# Keep this in mind for understanding two while loops.


# What is the purpose of first while loop?
# For the current prefix sum B[i], it covers all subarray ending at A[i-1].
# We want know if there is a subarray, which starts from an index, ends at A[i-1] and has at least sum K.
# So we start to compare B[i] with the smallest prefix sum in our deque, which is B[D[0]], hoping that [i] - B[d[0]] >= K.
# So if B[i] - B[d[0]] >= K, we can update our result res = min(res, i - d.popleft()).
# The while loop helps compare one by one, until this condition isn't valid anymore.


# Why we pop left in the first while loop?
# This the most tricky part that improve my solution to get only O(N).
# D[0] exists in our deque, it means that before B[i], we didn't find a subarray whose sum at least K.
# B[i] is the first prefix sum that valid this condition.
# In other words, A[D[0]] ~ A[i-1] is the shortest subarray starting at A[D[0]] with sum at least K.
# We have already find it for A[D[0]] and it can't be shorter, so we can drop it from our deque.


# What is the purpose of second while loop?
# To keep B[D[i]] increasing in the deque.


# Why keep the deque increase?
# If B[i] <= B[d.back()] and moreover we already know that i > d.back(), it means that compared with d.back(),
# B[i] can help us make the subarray length shorter and sum bigger. So no need to keep d.back() in our deque.





class Solution:
    def shortestSubarray(self, A, K):
        d = collections.deque([[0, 0]])
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i + 1 - d.popleft()[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i + 1, cur])
        return res if res < float('inf') else -1

                


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        d = collections.deque([[0, 0]])
        res, cur = len(A)+1, 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i + 1 - d.popleft()[0])
            while d and cur <= d[-1][1]: # new i make the further subarray length shorter and sum bigger 
                d.pop()
            d.append([i + 1, cur])
        return res if res < len(A)+1 else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        prefix = [0] * (len(A) + 1)
        for i in range(len(A)):
            prefix[i + 1] = prefix[i] + A[i]
            
        
        ans = sys.maxsize 
        deque = collections.deque([])
        
        for i in range(len(A) + 1):
            while deque and prefix[i] - prefix[deque[0]] >= K:
                ans = min(ans, i - deque[0])
                deque.popleft()
            while deque and prefix[i] <= prefix[deque[-1]]:
                deque.pop()
            deque.append(i)
            
        return ans if ans != sys.maxsize else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        if max(A) >= K:
            return 1
        n = len(A)
        prefix = [0] + list(itertools.accumulate(A))
        res = n+1
        dq = deque()
        for y, py in enumerate(prefix):
            while dq and prefix[dq[-1]] > py:
                dq.pop()
            while dq and py - prefix[dq[0]] >= K:
                res = min(res, y-dq.popleft())
            dq.append(y)
        return res if res <= n else -1

class Solution(object):
    def shortestSubarray(self, A, K):
        n = len(A)
        pref = [0]*(n+1)
        for i in range(1, n+1):
            pref[i] = pref[i-1] + A[i-1]
        
        node = deque(); ans = n + 1
        for i in range(len(pref)):
            while node and pref[i] - pref[node[0]] >= K:
                ans = min(ans, i-node[0])
                node.popleft()
            while node and pref[i] <= pref[node[-1]]:
                node.pop()
            node.append(i)
        
        return ans if ans < n+1 else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        ans = len(A) + 1
        S = deque()
        S.append([0, -1])
        for i, x in enumerate(A):
            cur = S[-1][0] + x
            while S and S[-1][0] >= cur:
                S.pop()
            S.append([cur, i])
            while S[-1][0] >= S[0][0] + K:
                ans = min(ans, S[-1][1] - S.popleft()[1])
                
        return ans if ans <= len(A) else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        d = collections.deque([[0, 0]])
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i + 1 - d.popleft()[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i + 1, cur])
            
        return res if res != float('inf') else -1

class Solution(object):
    def shortestSubarray(self, A, K):
        n = len(A)
        d = collections.deque([(A[0],0)])
        res = n+1
        
        for i in range(1, n):
            A[i] += A[i-1]
        A = [0] + A
        for i in range(n+1):
            while d and d[-1][0] > A[i]: d.pop()
            d.append((A[i], i))
            while d and A[i] - d[0][0] >= K:
                res = min(res, i-d[0][1])
                d.popleft()
            
        return res if res <= n else -1
                
        


from heapq import heappush, heappop
def kmin(a,k):
    cur_sum = 0
    h = [(0, -1)]
    min_ = float('inf')
    for i in range(0, len(a)):
        cur_sum +=a[i]
        while h and h[0][0]<=cur_sum-k:
            min_ = min(min_, i-h[0][1])
            heappop(h)
        heappush(h, (cur_sum, i))
    return min_ if min_ != float('inf') else -1
from collections import deque
def ksumalt(a,k):
    q = deque()
    q.append((-1, 0))
    cur_sum = 0
    min_len = float('inf')
    for i in range(len(a)):
        cur_sum += a[i]
        while q and cur_sum - q[0][-1] >=k:
            min_len = min(min_len, i-q[0][0])
            q.popleft()
        while q and cur_sum <= q[-1][-1]:
            q.pop()
        q.append((i, cur_sum))
    return -1 if min_len == float('inf') else min_len
class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        return ksumalt(A, K)

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        p,n = [0],len(A)
        for i in range(n):
            p.append(p[-1]+A[i])
        # p[i] = A[0]+A[1]+...+A[i-1]
        # p[j]-p[i] = sum(A[i:j])
        i,ret = 0,float('inf')
        q = collections.deque()
        while i < n+1:
            while q and p[q[-1]] > p[i]:
                q.pop()
            q.append(i)
            while q and p[q[-1]] - p[q[0]] >= K:
                ind = q.popleft()
                ret = min(ret,q[-1]-ind)
            i += 1
        return ret if ret!=float('inf') else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        n, store = len(A), [0]
        for x in A: store.append(store[-1] + x)
        res = n + 1
        queue = deque()
        for i, x in enumerate(store):
            while queue and x <= store[queue[-1]]: queue.pop()
            while queue and x - store[queue[0]] >= K: res = min(res, i-queue.popleft())
            queue.append(i)

        return res if res < n + 1 else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        if K == 0:
            return 0
        if not A:
            return -1
        if len(A) == 1:
            if A[0] >= K:
                return 1
            return 0
        from collections import deque
        ret = float('inf')
        for element in A:
            if element >= K:
                return 1
        for i in range(1, len(A)):
            A[i] += A[i-1]
        current_ele = deque()
        current_ele.append((-1, 0))
        for i, element in enumerate(A):
            while current_ele and current_ele[-1][1] >= element:
                current_ele.pop()
            current_ele.append((i, element))
            while current_ele[-1][1] >= current_ele[0][1]+K:
                ret = min(ret, current_ele[-1][0]-current_ele[0][0])
                current_ele.popleft()
        return ret if ret != float('inf') else -1

from collections import deque


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        d = deque()
        n = len(A)
        res = n+1

        prefixArr = [0] * (n + 1)

        for i in range(n):
            prefixArr[i + 1] = A[i] + prefixArr[i]

        for end in range(n+1):
            while d and prefixArr[end] - prefixArr[d[0]] >= K:
                res = min(res, end - d.popleft())
            while d and prefixArr[d[-1]] >= prefixArr[end]:
                d.pop()
            d.append(end)

        return -1 if res == n+1 else res



class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        deq = collections.deque([])
        prefix = [0]
        res = float('inf')
        for a in A:
            prefix.append(prefix[-1] + a)
        for i, x in enumerate(prefix):
            while deq and prefix[deq[-1]] >= x:
                deq.pop()
            while deq and prefix[deq[0]] <= x - K:
                res = min(res, i - deq.popleft())
            deq.append(i)
        return res if res < float('inf') else -1       

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        P = [0]
        for x in A:
            P.append(P[-1] + x)
        
        q = collections.deque()
        min_length_K = -1
        for j, Pj in enumerate(P):
            while len(q) > 0 and P[q[-1]] >= Pj:
                q.pop()
            while len(q) > 0 and Pj - P[q[0]] >= K:
                if min_length_K == -1 or j - q[0] < min_length_K:
                    min_length_K = j - q[0]
                q.popleft()
            q.append(j)
            
        return min_length_K

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        d = collections.deque([[0, 0]])
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i + 1 - d.popleft()[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i + 1, cur])
        return res if res < float('inf') else -1        

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        #First check this problem >> https://leetcode.com/problems/minimum-size-subarray-sum/
        #>>> Important <<<<
        #https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/262641/Python-Prefix-Sum-and-Sliding-Window
        #As left and right index keeps increasing, time complexity is O(N).
        n = len(A)
        res = n+1
        Sum = 0
        dq  = collections.deque([(-1,0)]) #-1 for index, 0 for sum 
        
        for i, val in enumerate(A):
            Sum += val
            if val > 0:
                while dq and Sum - dq[0][1] >= K:
                    res = min(res, i-dq.popleft()[0])
            else:
                while dq and Sum < dq[-1][1]:
                    dq.pop()
            dq.append((i, Sum))
            
        if res <= n:
            return res
        else:
            return -1
        


from collections import deque

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        dq = deque()
        pre = [0]
        l = len(A)
        ans = l+1
        for i in range(l):
            pre.append(pre[-1] + A[i])
        for i in range(l+1):
            while dq and pre[dq[-1]] >= pre[i]:
                dq.pop()
            while dq and pre[dq[0]] + K  <= pre[i]:
                ans = min(ans, i-dq.popleft())
            dq.append(i)
        #print(ans)
        return (ans if ans < l+1 else -1)

from collections import deque


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        if max(A) >= K:
            return 1
        
        if K <= 0:
            return -1
            
        psum = [0]
        for a in A:
            psum.append(psum[-1] + a)
            
        window = deque([(0, 0)])
        res = float('inf')
        for right in range(len(A)):
            while window and psum[right + 1] <= window[-1][1]:
                window.pop()
            
            window.append((right + 1, psum[right + 1]))
            while window and window[-1][1] - window[0][1] >= K:
                res = min(res, window[-1][0] - window[0][0])
                window.popleft()
        
        return res if res != float('inf') else -1


class Solution:
    def shortestSubarray(self, nums: List[int], K: int) -> int:
        sum1=0
        flag=False
        min1=float('inf')
        cums=[0]
        dq=collections.deque()
        
        for i in range(len(nums)):
            cums.append(cums[-1]+nums[i])
        print(cums)
        
        for i in range(len(nums)+1):
            while dq and cums[i]-cums[dq[0]]>=K:
                val=dq.popleft()
                min1=min(min1,i-val)
            while dq and cums[i]<=cums[dq[-1]]:
                dq.pop()
            dq.append(i)
                
                #This loop is used because if there is [2,-1,2] and K=3 for cums=[0,2,1,3] we know that from 2 to 1 the value decreased from 1 to x increased so the min will be from 1 to x rather than 2 to x so eliminated(because length b/w 1 to x < 2 to x)
            
            
        if min1==float('inf'):
            return -1
        return min1
                


from collections import deque
class Solution:    
    def shortestSubarray(self, A: List[int], K: int) -> int:
        n=len(A)
        prefix_sum= [0 for _ in range(n+1)]
        for i in range(1,len(prefix_sum)):
            prefix_sum[i] = prefix_sum[i-1]+ A[i-1]
        dq= deque()
        ans=n+1
        for i in range(len(prefix_sum)):
            while dq and prefix_sum[i]-prefix_sum[dq[0]]>=K:
                ans = min(ans,i-dq[0])
                dq.popleft()
            while dq and prefix_sum[i]<=prefix_sum[dq[-1]]:
                dq.pop()        
            dq.append(i)
        return -1 if ans==n+1 else ans

from collections import deque


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        prefix_arr = [0]
        for i in range(len(A)):
            prefix_arr.append(prefix_arr[i] + A[i])

        deq = deque()
        result = len(A) + 1

        for i in range(len(prefix_arr)):
            while len(deq) > 0 and prefix_arr[i] < prefix_arr[deq[-1]]:
                deq.pop()
            deq.append(i)

            while len(deq) > 0 and prefix_arr[deq[-1]] - prefix_arr[deq[0]] >= K:
                result = min(result, deq[-1]-deq[0])
                deq.popleft()

        if result == len(A) + 1:
            return -1

        return result


import heapq

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        q = [(0, -1)]
        cum = 0
        res = float('inf')
        for i, x in enumerate(A):
            cum += x
            
            while q and cum - q[0][0] >= K:
                res = min(res, i - heapq.heappop(q)[1])
                
            heapq.heappush(q, (cum, i))
        return res if res < float('inf') else -1
        
        


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        Sum, res, heap, flag = 0, len(A), [(0, -1)], False
        
        for i, v in enumerate(A):
            Sum += v
            while heap and Sum - heap[0][0] >= K:
                flag = True
                res = min(res, i - heapq.heappop(heap)[1])
            heapq.heappush(heap, (Sum, i))
        
        return res if flag else -1
            


from heapq import heappush, heappop
def kmin(a,k):
    cur_sum = 0
    h = [(0, -1)]
    min_ = float('inf')
    for i in range(0, len(a)):
        cur_sum +=a[i]
        while h and h[0][0]<=cur_sum-k:
            min_ = min(min_, i-h[0][1])
            heappop(h)
        heappush(h, (cur_sum, i))
    return min_ if min_ != float('inf') else -1
        
class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        return kmin(A, K)

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        queue = collections.deque()
        Sum, res = 0, float('inf')
        queue.append((0, -1))
        for i, v in enumerate(A):
            Sum += v
            
            while queue and Sum - queue[0][0] >= K:
                res = min(res, i - queue.popleft()[1])
            while queue and Sum <= queue[-1][0]:
                queue.pop()
            queue.append((Sum, i))
            
        return res if res < float('inf') else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        cumsum = itertools.accumulate(A)
        
        mono = collections.deque([(0, -1)])
        result = math.inf
        for ind, val in enumerate(cumsum):
            while mono and mono[-1][0] >= val:
                mono.pop()
            mono.append((val, ind))
            
            while val - mono[0][0] >= K:
                result = min(result, ind - mono.popleft()[1])
        
        if result == math.inf:
            return -1
        else:
            return result

from collections import deque


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        psum = [0]
        for a in A:
            psum.append(psum[-1] + a)
            
        window = deque([(0, 0)])
        res = float('inf')
        for right in range(len(A)):
            while window and psum[right + 1] <= window[-1][1]:
                window.pop()
            
            window.append((right + 1, psum[right + 1]))
            while window and window[-1][1] - window[0][1] >= K:
                res = min(res, window[-1][0] - window[0][0])
                window.popleft()
        
        return res if res != float('inf') else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        # Step 1: create a prefix (left) sum for the array
        n = len(A)
        if n == 0:
            return -1
        dp = [0] * (n + 1)  # dp[i] is the sum of A[0: i]
        for i in range(1, n+1):
            dp[i] = dp[i-1] + A[i-1]
        
        # Step 2: iterate over a monotonic (increasing) queue, whenever a new
        # prefix sum is >= most left ele + K, left pop
        queue = collections.deque()
        queue.append((0, 0))  # First ele is the index, second ele in the dop array
        
        # The minimum of the sequence length
        res = (n + 1)

        for i in range(1, n+1):
            # Check if dp[i] minus the left end is no less than K
            while queue:
                qi, qe = queue[0]
                if qe  + K <= dp[i]:
                    res = min(res, i - qi)
                    queue.popleft()
                else:
                    break
            
            # Update the monotonic queue
            while queue:
                _, qe = queue[-1]
                if qe >= dp[i]:
                    queue.pop()
                else:
                    break
            queue.append((i, dp[i]))

        if res == (n+1):
            return -1
        else:
            return res
            


class Solution:
    def shortestSubarray(self, A: List[int], k: int) -> int:
        s = collections.deque()    # Inc    # (sum, ind)
        curr = 0
        ans = math.inf
        for i in range(len(A)):
            curr += A[i]
            if curr>=k: ans=min(ans, i+1)
            while s and curr - s[0][0]>=k:
                ans = min(ans, i-s.popleft()[1])
            while s and s[-1][0]>curr:
                s.pop()
            s.append((curr, i))
        
        return ans if ans!=float('inf') else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        dq = deque([(0,0)])
        res = float('inf')
        p = 0
        for i, a in enumerate(A):
            p += a
            while dq and p<=dq[-1][0]:
                dq.pop()
                
            while dq and p-dq[0][0]>=K:
                res = min(res, i+1-dq.popleft()[1])
                
            dq.append((p, i+1))
            
        return res if res!=float('inf') else -1
        
                
                


from collections import deque
class Solution:
    def shortestSubarray(self, A: List[int], k: int) -> int:
        for ele in A:
            if ele>=k:
                return 1
        s=[0]
        for i in range(len(A)):
            s.append((s[-1] if len(s) else 0)+A[i])
        print(s)
        queue=deque()
        #queue.append((0,0))
        ans=float('inf')
        for i,e in enumerate(s):
            #print(queue)
            if len(queue)==0:
                queue.append((i,e))
                
            elif len(queue) and queue[-1][1]<e:
                
                if e-queue[0][1]>=k:
                    while len(queue) and e-queue[0][1]>=k:
                        ans=min(ans,i-queue[0][0])
                        queue.popleft()
                queue.append((i,e))
                
            elif len(queue) and queue[-1][1]>=e:
                while len(queue) and queue[-1][1]>=e:
                    queue.pop()
                queue.append((i,e))
        
        if len(queue)>1 and queue[-1][1]>=queue[0][1]+k:
            ans=min(ans,i-queue[-1][0])
            
        return -1 if ans==float('inf') else ans
                


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        Sum, res, heap, flag = 0, len(A), [(0, -1)], False
        
        for i, v in enumerate(A):
            Sum += v
            while heap and Sum - heap[0][0] >= K:
                flag = True
                res = min(res, i - heapq.heappop(heap)[1])
            
            heapq.heappush(heap, (Sum, i))
        
        return res if flag else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        queue = collections.deque([(0, 0)])
        cur_sum = 0
        res = len(A) +1
        
        for right, val in enumerate(A):
            cur_sum += val
            while queue and cur_sum - queue[0][1] >= K:
                res = min(res, right+1-queue.popleft()[0])
            while queue and queue[-1][1] >= cur_sum:
                queue.pop()
                
            queue.append((right+1, cur_sum))
                
        if res <= len(A):
            return res
        return -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        curr_sum = 0
        s_sum = []
        s_ind = []
        res = math.inf
        for i, num in enumerate(A):
            curr_sum += num
            while s_sum and s_sum[-1] >= curr_sum:
                s_sum.pop()
                s_ind.pop()
            
            if not s_sum:
                if curr_sum >= K:
                    res = min(res, i + 1)
            else:
                ind = bisect_right(s_sum, curr_sum - K)
                if ind - 1 >= 0:
                    res = min(res, i - s_ind[ind - 1])
                elif curr_sum >= K:
                    res = min(res, i + 1)
            
            s_sum.append(curr_sum)
            s_ind.append(i)
        
        return -1 if math.isinf(res) else res

import heapq
class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        prefix = 0
        pq = [[0, -1]]
        res = float('inf')
        for i, a in enumerate(A):
            prefix += a
            while pq and prefix - pq[0][0] >= K:
                res = min(res, i - heapq.heappop(pq)[1])
            heapq.heappush(pq, [prefix, i])
        return res if res < float('inf') else -1
            
        
#         prefix = [0]
#         for a in A:
#             prefix.append(prefix[-1] + a)
#         res = float('inf')
#         deq = collections.deque()
        
        
#         prefix = [0]
#         for a in A:
#             prefix.append(prefix[-1] + a)
#         res = float('inf')
#         deq = collections.deque()
#         for i, x in enumerate(prefix):
#             while deq and prefix[deq[-1]] >= x:
#                 deq.pop()
#             while deq and prefix[deq[0]] <= x - K:
#                 res = min(res, i - deq.popleft())
#             deq.append(i)
#         return res if res < float('inf') else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        prefix = [0] * (len(A)+1)
        for i in range(len(A)):
            prefix[i+1] = A[i] + prefix[i]
        
        ans = len(A) + 1
        monoq = deque()
        for i in range(len(prefix)):
            while monoq and prefix[i] <= prefix[monoq[-1]]:
                monoq.pop()
            while monoq and prefix[i] - prefix[monoq[0]]>=K:
                ans = min(ans, i-monoq.popleft())
                
            monoq.append(i)
            
        return ans if ans<len(A)+1 else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        running = [0]
        for num in A: 
            running.append(running[-1] + num)
            
        result = math.inf
        deque = collections.deque([0]) # left idx
        r = 1 
        
        while r < len(running): 
            if not deque: 
                deque.append(r)
                r += 1 
                continue 
                
            while deque and r < len(running) and running[r] - running[deque[0]] < K:
                        
                #pop the last of the queue if it is smaller to maintain mono increasing queue 
                while deque and running[r] <= running[deque[-1]]: 
                    deque.pop()
                    
                deque.append(r)
                r += 1 
            
            # right reached the end yet still not satisfied 
            if r == len(running): 
                break
                
            while deque and running[r] - running[deque[0]] >= K:
                l = deque.popleft()
                result = min(result, r-l)   
    
            # r += 1
            
        return result if result != math.inf else -1
            


        '''
        
                    #pop the last of the queue if it is smaller to maintain mono increasing queue 
                while deque and running[r] <= running[deque[-1]]: 
                    deque.pop()
                    
                    
        l = 0
        r = 1 
        
        while r < len(running): 
            
            while r < len(running) and running[r] - running[l] < K: 
                r += 1 
            while l < r and running[r] - running[l+1] >= K: 
                l += 1
            result = min(result, r-l)
            r += 1
            l  += 1
            
        return result
            
        
            while r < len(running): 
            while deque and running[r] - running[deque[0]] >= K:
                result = min(result, i-deque[0])
                deque.popleft()
            while deque and running[r] <= running[deque[-1]]:
                deque.pop()
            deque.append(r)
            
        return result if result != math.inf else -1
    
    
                
            while r < len(running)-1 and running[r] - running[l] < s: 
                r += 1 

            while l < r and running[r] - running[l] >= s:
                result = min(result, r-l)                
                l += 1
                
            r += 1
        '''


import bisect

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        cur, stack, idx, ans = 0, [0], [-1], float('inf')
        for i, x in enumerate(A):
            cur += x
            while len(stack) > 0 and stack[-1] >= cur:
                stack.pop()
                idx.pop()
            j = bisect.bisect_right(stack, cur - K)
            if j > 0:
                ans = min(ans, i - idx[j - 1])
            stack.append(cur)
            idx.append(i)
        
        if ans == float('inf'):
            return -1
        return ans
        


class Solution:
    def shortestSubarray(self, A, K):
        N, acc = len(A), [0]
        for v in A:
            acc.append(acc[-1] + v)
        ans, monoq = float('inf'), deque()
        for size, curS in enumerate(acc):
            while monoq and curS <= acc[monoq[-1]]:
                monoq.pop()
            while monoq and curS - acc[monoq[0]] >= K:
                ans = min(ans, size - monoq.popleft())
            monoq.append(size)
        return ans if ans != float('inf') else -1
    
from heapq import *
class Solution:
    def shortestSubarray(self, A, K):
        heap, curS, ans = [(0, -1)], 0, float('inf')
        for i, v in enumerate(A):
            curS += v
            while heap and curS - heap[0][0] >= K:
                ans = min(ans, i - heappop(heap)[1])
            heappush(heap, (curS, i))
        return ans if ans != float('inf') else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        '''
        idea 1: sliding window:
                   r      
        [2, -1, 2, 3] 4
             l. 
        if cur_sum > k -> move l otherwise move r
        '''
        P = [0]
        for x in A:
            P.append(P[-1] + x)
        # the largest i for j such that  A[j] - A[i] >= k
        # [2, -1, 2, 3]  -> [0, 2, 1, 3, 5]
        # [0, 1, 3, 5]
        # 
        ans = len(A)+1
        dq = collections.deque([])
        for i, y in enumerate(P):
            while dq and y < P[dq[-1]]:
                dq.pop()
            while dq and y - P[dq[0]] >= K:
                ans = min(ans, i - dq.popleft())
            dq.append(i)
        return ans if ans < len(A)+1 else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        if not A:
            return -1
        
        if len(A) == 1:
            if A[0] < K:
                return -1
            return 1
        
        min_length = float('inf')
        temp = [0]
        for i in A:
            temp.append(i + temp[-1])
        queue = []
        
        for c, v in enumerate(temp):
            
            while queue and v <= temp[queue[-1]]:
                queue.pop()
                
            while queue and v-temp[queue[0]] >= K:
                min_length = min(min_length, c-queue.pop(0))
                
            queue.append(c)
            
        if min_length == float('inf'):
            return -1
        return min_length
        


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        # algorihtm
        # find the minimum length of the subarray, where there sum >= k
        # when dealing sum, sum prifix?
        
        # sliding window -classis?  O(N^2)
        # holding a deque ?yes
        #   decreasing or increasing?
        #   decresaing? X    no need to save the one before  ==> choose increasing
        #   save number or index??? we need to i - index, so save index in deque
        #   when add / delete our dequeue: 
        #          add ==> in for loop
        #          delete ==> sum_[i] <= sum_[queue[-1]], pop()
        #                     sum_[i] - sum_[deque[0]] >= K, pop(0)
        
        # deque
        sum_ = [0]
        for num in A:
            sum_.append(sum_[-1] + num)
        result = len(A)+1
        deque = []
        for i,num in enumerate(sum_):
            while(deque and num <= sum_[deque[-1]]):
                deque.pop()
            while(deque and num - sum_[deque[0]] >= K):
                result = min(result, i - deque[0])
                deque.pop(0)
            deque.append(i)
                
        return result if result != len(A)+1 else -1
        




class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        Sum, res, heap, flag = 0, len(A), [(0, -1)], False
        for i, v in enumerate(A):
            Sum += v
            while heap and Sum - K >= heap[0][0]:
                flag = True
                res = min(res, i - heapq.heappop(heap)[1])
            heapq.heappush(heap, (Sum, i))
        return res if flag else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        N = len(A)
        P = [0]
        for x in A:
            P.append(P[-1] + x)

        ans = N+1 # N+1 is impossible
        monoq = [] #opt(y) candidates, represented as indices of P
        for y, Py in enumerate(P):
            #Want opt(y) = largest x with Px <= Py - K
            while monoq and Py <= P[monoq[-1]]:
                monoq.pop()

            while monoq and Py - P[monoq[0]] >= K:
                ans = min(ans, y - monoq.pop(0))

            monoq.append(y)

        return ans if ans < N+1 else -1

class Solution:
    def shortestSubarray(self, A, K):
        from heapq import heappush,heapify,heappop
        heap = []
        length = float('inf')
        summation = 0
        heapify(heap)
        heappush(heap,[0,-1])
        for i,number in enumerate(A):
            summation += number
            difference = summation - K
            while heap and (heap[0][0] <=difference or i - heap[0][1] >= length):
                previous_summation , previous_index = heappop(heap)
                length = min(length,i - previous_index)
            heappush(heap,[summation,i])
        return length if length != float('inf') else -1

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        nums = [0] + nums
        
        deque = [ (0,0) ]
        cur = 0
        res = 1+len(nums)
        
        for i in range(1,len(nums)):
            #print(deque)
            cur += nums[i]
            while deque and cur-deque[0][1]>=k :
                res = min(res,i-deque[0][0])
                deque.pop(0)
                
            while deque and deque[-1][1]>=cur:
                deque.pop(-1)
                
            deque.append( (i,cur) )
        
        if res>len(nums):
            return -1
        return res
    



class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        if len(A) == 1:
            
            return 1 if A[0] <= K else -1
        
        min_len = len(A) + 1
        
        dq = []
        
        pref = [0]
        
        for i in range(len(A)):
            
            pref.append(pref[- 1] + A[i])
            
        for i in range(len(pref)):
            
            # print(dq)
            
            while dq and pref[i] <= pref[dq[-1]]:
                
                dq.pop(-1)
                
            while dq and pref[i] - pref[dq[0]] >= K:
                
                min_len = min(min_len, i - dq[0])
                
                dq.pop(0)
                
            dq.append(i)
            
        return min_len if min_len < len(A) + 1 else -1

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        N = len(A)
        P = [0]
        for x in A:
            P.append(P[-1] + x)

        #Want smallest y-x with Py - Px >= K
        ans = N+1 # N+1 is impossible
        monoq = collections.deque() #opt(y) candidates, represented as indices of P
        for y, Py in enumerate(P):
            #Want opt(y) = largest x with Px <= Py - K
            while monoq and Py <= P[monoq[-1]]:
                monoq.pop()

            while monoq and Py - P[monoq[0]] >= K:
                ans = min(ans, y - monoq.popleft())

            monoq.append(y)

        return ans if ans < N+1 else -1

from collections import deque

class Solution:
    def shortestSubarray(self, A, K):
        possible_starts = deque([0])
        
        prefix_sums = [0 for i in range(len(A) + 1)]
        for i in range(len(A)):
            prefix_sums[i + 1] = prefix_sums[i] + A[i]
       
        shortest_found = len(A) + 1
        curr_sum = 0
        for i in range(len(A) + 1):
            while len(possible_starts) > 0 and prefix_sums[i] - prefix_sums[possible_starts[0]] >= K:
                shortest_found = min(shortest_found, i - possible_starts.popleft())
            while len(possible_starts) > 0 and prefix_sums[i] <= prefix_sums[possible_starts[-1]]:
                possible_starts.pop()
            possible_starts.append(i)
        return shortest_found if shortest_found <= len(A) else -1

import heapq
class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        '''
        idea 1: sliding window:
                   r      
        [2, -1, 2, 3] 4
             l. 
        if cur_sum > k -> move l otherwise move r
        
        longest?
        [0, 2, -3, 5]   5
        '''
        P = [0]
        for x in A:
            P.append(P[-1] + x)
            
        # the largest i for j such that  A[j] - A[i] >= k
        # [2, -1, 2, 3]  -> [0, 2, 1, 3, 5]    k =3
        #                   [0, 1 ]
        # [0, 1, 3, 5]
        # [0, 2, 1, 3, 5]
        # [1, 3]
         # 
        '''
        heapq[1, 2, 3]
        
        '''

        heap = []
        min_l = len(A)+1
        for i, num in enumerate(P):
            while heap and num - heap[0][0] >= K:
                v , idx =  heapq.heappop(heap)
                min_l = min(min_l, i-idx)
            heapq.heappush(heap, (num, i))
        return min_l if min_l < len(A)+1 else -1
        # ans = len(A)+1
        # dq = collections.deque([])
        # for i, y in enumerate(P):
        #     while dq and y < P[dq[-1]]:
        #         dq.pop()
        #     while dq and y - P[dq[0]] >= K:
        #         ans = min(ans, i - dq.popleft())
        #     dq.append(i)
        # return ans if ans < len(A)+1 else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        mx = sys.maxsize
        if A[0] == K:
            return 1
        for i in range(1, len(A)):
            A[i] += A[i-1]
            if A[i] >= K:
                mx = min(mx, i+1)
                
        st = [0]
        for i in range(1, len(A)):
            while len(st) and A[i] - A[st[0]] >= K:
                popped = st.pop(0)
                mx = min(mx, i - popped)
                
            while len(st) and A[i] <= A[st[-1]]:
                st.pop()
                
            st.append(i)
        return mx if mx != sys.maxsize else -1
        '''
        d = []
        o = []
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            o.append(cur)
            while d and cur - d[0][1] >= K:
                res = min(res, i - d.pop(0)[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i, cur])
        print(o)
        return res if res < float('inf') else -1
    '''
                
                
        
        
        


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        d = [[0, 0]]
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i-d.pop(0)[0]+1)
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i+1, cur])
        return res if res < float('inf') else -1

from collections import deque

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        # prefix_sums[i] == sum(A[:i - 1])
        prefix_sums = [0]
        for num in A:
            prefix_sums.append(prefix_sums[-1] + num)
        
        shortest_length = math.inf
        # a deque of indices i_1, ..., i_k s.t. P[i_1] <= P[i_2] ...
        cands = deque()
        for i, prefix_sum in enumerate(prefix_sums):
            while len(cands) > 0 and prefix_sum <= prefix_sums[cands[-1]]:
                cands.pop()
            while len(cands) > 0 and prefix_sum - prefix_sums[cands[0]] >= K:
                shortest_length = min(shortest_length, i - cands.popleft())
            cands.append(i)
        
        return shortest_length if shortest_length != math.inf else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        prefixSum = [0]*(len(A)+1)
        for i in range(1,len(prefixSum)):
            prefixSum[i] = prefixSum[i-1]+A[i-1]
        
        dq = deque()
        shortestLen = sys.maxsize
        
        for i in range(len(prefixSum)):
            while dq and prefixSum[dq[-1]] >= prefixSum[i]:
                dq.pop()
            
            while dq and prefixSum[i]-prefixSum[dq[0]] >= K:
                shortestLen = min(shortestLen,i-dq[0])
                dq.popleft()
            
            dq.append(i)
        return shortestLen if shortestLen != sys.maxsize else -1


from collections import deque

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        
        n = len(A)
        B = [0 for _ in range(n+1)]
        for i in range(n):
            B[i+1] = A[i] + B[i]
        
        res = n+1
        d = deque()
        for j in range(n+1):
            while d and B[j] - B[d[0]] >= K:
                res = min(res, j - d[0])
                d.popleft()
            while d and B[d[-1]] > B[j]:
                d.pop()
            d.append(j)
            
        return res if res <= n else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        p = [0]
        p[0] = A[0]
        for i in range(1,len(A)):
            p.append(p[i-1] + A[i])
        
        s = []
        s.append((-1,0))
        min_len = float('inf')
        for i in range(len(p)):
            while s and  p[i] - s[0][1] >= K:
                min_len = min(min_len, i - s[0][0])
                s.pop(0)
                
                
            while s and p[i] <= s[-1][1]:
                s.pop()
            
            s.append((i,p[i]))
            
        if min_len != float('inf'):
            return min_len
        else:
            return -1
            
                
            
        
            
            
            
            
                
                
            
                    
                
                
            


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        ans = 1 if A[0] >= K else sys.maxsize
        
        
        for i in range(1, len(A)):
            A[i] += A[i-1]
            if A[i] >= K:
                ans = min(ans, i+1)
        
        
        st = [(A[0],0)]
        for i in range(1, len(A)):
            while len(st) and A[i] - st[0][0] >= K:
                ans = min(ans, i - st[0][1])
                st.pop(0)
                
            while len(st) and A[i] <= st[-1][0]:
                st.pop()

            st.append((A[i], i))
            
        return ans if ans != sys.maxsize else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        psum = 0
        total = 0
        dq = deque([(0,-1)])
        res = float('inf')
        for i, a in enumerate(A):
            psum += a
            # print(dq, i, a, psum)
            while dq and dq[-1][0]>psum:
                dq.pop()
            
            while dq and psum-dq[0][0]>=K:
                res = min(res, i-dq.popleft()[1])
            #  print(dq, res)  
            dq.append((psum, i))
        # print(dq)
        return res if res!=float('inf') else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        '''
        monoqueue + prefixsum + sliding window
        '''
        n = len(A)
        prefix_sum = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
        end = 0
        res = float('inf')
        mono_queue = collections.deque()
        while end < n + 1:
            while mono_queue and prefix_sum[mono_queue[-1]] >= prefix_sum[end]:
                mono_queue.pop()
            while mono_queue and prefix_sum[end] - prefix_sum[mono_queue[0]] >= K:
                start_index = mono_queue.popleft()
                res = min(res, end - start_index)
            mono_queue.append(end)
            end += 1
        return res if res != float('inf') else -1


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        mx = sys.maxsize
        if A[0] == K:
            return 1
        for i in range(1, len(A)):
            A[i] += A[i-1]
            if A[i] >= K:
                mx = min(mx, i+1)
                
        st = [0]

        for i in range(1, len(A)):
            while len(st) and A[i] - A[st[0]] >= K:
                popped = st.pop(0)
                mx = min(mx, i - popped)
                
            while len(st) and A[i] <= A[st[-1]]:
                st.pop()
                
            st.append(i)
        return mx if mx != sys.maxsize else -1
        '''
        d = []
        o = []
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            o.append(cur)
            while d and cur - d[0][1] >= K:
                res = min(res, i - d.pop(0)[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i, cur])
        print(o)
        return res if res < float('inf') else -1
    '''
                
                
        
        
        


class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        total = 0
        q = deque()
        q.append([-1, 0])

        res = float('inf')
        for i, v in enumerate(A):
            total += v
            #print(q[0])
         
                
            while q and total < q[-1][1]:
                q.pop()
                
            q.append([i, total])
            while q and total - q[0][1] >=K:
                res = min(res, i - q[0][0])
                q.popleft()

        return res if res != float('inf') else -1