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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Sorting

Amortized analysis

Range queries

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:
				while queue and cum_sum - queue[0][1] >= K:
					e = queue.popleft()
					result = min(result, i - e[0])
			else:
				while queue and cum_sum <= queue[-1][1]:
					e = queue.pop()
			queue.append((i, cum_sum))
		return result if result <= len(A) else -1


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


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

	def shortestSubarray(self, A: List[int], k: int) -> int:
		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)
		return out if out != sys.maxsize 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
		pq = []
		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]])
		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


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:
			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)
		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)
		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:
		N = len(A)
		P = [0]
		for x in A:
			P.append(P[-1] + 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)
		return ans if ans < N + 1 else -1


class Solution:

	def shortestSubarray(self, arr, k):
		n = len(arr)
		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:
		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


class Solution:

	def shortestSubarray(self, A: List[int], K: int) -> int:
		prefix_sums = [0]
		prefix_sum = 0
		for a in A:
			prefix_sum += a
			prefix_sums.append(prefix_sum)
		from collections import deque
		mono_q = deque()
		min_len = len(A) + 1
		for (y, Py) in enumerate(prefix_sums):
			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:
		pre = [0]
		n = len(A)
		for num in A:
			pre.append(num + pre[-1])
		ans = n + 1
		stack = deque()
		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:
		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


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:
		p = [0]
		for i in range(len(A)):
			p.append(p[-1] + A[i])
		q = []
		result = len(A) + 1
		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()
			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:

	def shortestSubarray(self, A: List[int], K: int) -> int:
		preSum = [0]
		for e in A:
			preSum.append(preSum[-1] + e)
		min_len = sys.maxsize
		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


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]:
				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(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(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])
		(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


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:
		n = len(A)
		res = n + 1
		Sum = 0
		dq = collections.deque([(-1, 0)])
		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)
		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)
		if min1 == float('inf'):
			return -1
		return min1


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


class Solution:

	def shortestSubarray(self, A: List[int], K: int) -> int:
		n = len(A)
		if n == 0:
			return -1
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			dp[i] = dp[i - 1] + A[i - 1]
		queue = collections.deque()
		queue.append((0, 0))
		res = n + 1
		for i in range(1, n + 1):
			while queue:
				(qi, qe) = queue[0]
				if qe + K <= dp[i]:
					res = min(res, i - qi)
					queue.popleft()
				else:
					break
			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()
		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


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()
		ans = float('inf')
		for (i, e) in enumerate(s):
			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:
		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


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])
		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):
				while deque and running[r] <= running[deque[-1]]:
					deque.pop()
				deque.append(r)
				r += 1
			if r == len(running):
				break
			while deque and running[r] - running[deque[0]] >= K:
				l = deque.popleft()
				result = min(result, r - l)
		return result if result != math.inf else -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:
		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:
		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, 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)):
			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)):
			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


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:
		P = [0]
		for x in A:
			P.append(P[-1] + x)
		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


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


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 = [0]
		for num in A:
			prefix_sums.append(prefix_sums[-1] + num)
		shortest_length = math.inf
		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