You are given a sequence of n integers a1, a2, ..., an and an integer d.
Find the length of the shortest non-empty contiguous subsequence with sum of elements at least d. Formally, you should find the smallest positive integer k with the following property: there is an integer s (1 ≤ s ≤ N-k+1) such that as + as+1 + ... + as+k-1 ≥ d.

-----Input-----

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers n and d.
- The second line contains n space-separated integers a1, a2, ..., an.

-----Output-----
For each test case, print a single line containing one integer — the length of the shortest contiguous subsequence with sum of elements ≥ d. If there is no such subsequence, print -1 instead.

-----Constraints-----
- 1 ≤ T ≤ 105
- 1 ≤ n ≤ 105
- -109 ≤ d ≤ 109
- -104 ≤ ai ≤ 104
- 1 ≤ sum of n over all test cases ≤ 2 · 105

-----Example-----
Input:

2
5 5
1 2 3 1 -5
5 1
1 2 3 1 -5

Output:

2
1

Source: codechef | Difficulty: VERY_HARD
Tags: Divide and conquer

Complete search


Solutions:
T = int(input())
for test in range(T):
	(n, d) = [int(v) for v in input().split()]
	A = [int(v) for v in input().split()]
	if d <= 0:
		if max(A) >= d:
			print(1)
		else:
			print(-1)
		continue
	tot = 0
	hist = [(0, 0)]
	best = float('inf')
	ind = -1
	for i in range(n):
		while hist and tot <= hist[-1][0]:
			hist.pop()
			if ind == len(hist):
				ind -= 1
		hist.append((tot, i))
		tot += A[i]
		while ind < len(hist) - 1 and hist[ind + 1][0] <= tot - d:
			ind += 1
		if ind > -1 and best > i - hist[ind][1] + 1:
			best = i - hist[ind][-1] + 1
	if best < float('inf'):
		print(best)
	else:
		print(-1)


from collections import deque
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	pref = [0]
	for i in range(1, n + 1):
		pref.append(a[i - 1] + pref[i - 1])
	ff = 0
	ss = 1
	ans = -1
	nex_smal = deque([])
	while ss <= n and ff <= n:
		if pref[ss] > pref[ff]:
			if pref[ss] - pref[ff] >= d:
				if ans == -1:
					ans = ss - ff
				else:
					ans = min(ans, ss - ff)
				if len(nex_smal) == 0:
					ff += 1
				else:
					ff = nex_smal[0]
					nex_smal.popleft()
				continue
		else:
			ff = ss
			if a[ff - 1] >= d:
				ans = 1
		if len(nex_smal) == 0:
			nex_smal.append(ss)
		else:
			while pref[nex_smal[-1]] > pref[ss]:
				nex_smal.pop()
				if len(nex_smal) == 0:
					break
			nex_smal.append(ss)
		ss += 1
	print(ans)


import collections

def shortestSubarray(A, K):
	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):
		if not monoq:
			if Py >= K:
				return 1
		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
for t in range(int(input())):
	(N, D) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	print(shortestSubarray(A, D))


for _ in range(int(input())):
	(n, d) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	prefix = [(0, -1)]
	tot = 0
	ans = n + 1
	for i in range(n):
		tot += arr[i]
		while prefix and prefix[-1][0] >= tot:
			prefix.pop()
		(lo, hi) = (0, len(prefix))
		diff = tot - d
		while lo < hi:
			mid = lo + hi >> 1
			if prefix[mid][0] > diff:
				hi = mid
			else:
				lo = mid + 1
		if lo == len(prefix):
			lo -= 1
		if prefix and prefix[lo][0] > diff:
			lo -= 1
		if prefix and lo >= 0:
			ans = min(ans, i - prefix[lo][1])
		prefix.append((tot, i))
	if ans == n + 1:
		ans = -1
	print(ans)