Given an array of integers arr and an integer target.
You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.
Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.
 
Example 1:
Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:
Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:
Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

Example 4:
Input: arr = [5,5,4,4,5], target = 3
Output: -1
Explanation: We cannot find a sub-array of sum = 3.

Example 5:
Input: arr = [3,1,1,1,5,1,2,1], target = 3
Output: 3
Explanation: Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.

 
Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 1000
1 <= target <= 10^8

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Sorting

Amortized analysis

Starter code: class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        

Solutions:
class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		(i, window, result) = (0, 0, float('inf'))
		premin = [float('inf')] * len(arr)
		for (j, num) in enumerate(arr):
			window += num
			while window > target:
				window -= arr[i]
				i += 1
			if window == target:
				curr = j - i + 1
				result = min(result, curr + premin[i - 1])
				premin[j] = min(curr, premin[j - 1])
			else:
				premin[j] = premin[j - 1]
		return result if result < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		dp = [float('inf')] * n
		ans = float('inf')
		s = 0
		j = 0
		for i in range(n):
			s += arr[i]
			while s > target:
				s -= arr[j]
				j += 1
			if s == target:
				cur = i - j + 1
				ans = min(ans, cur + dp[j - 1])
				dp[i] = min(cur, dp[i - 1])
			else:
				dp[i] = dp[i - 1]
		return ans if ans < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		if not arr:
			return -1

		def getMinSub(arr, target):
			dp = [float('inf')] * len(arr)
			total = 0
			lookup = defaultdict(int)
			for (index, val) in enumerate(arr):
				total += val
				if total == target:
					dp[index] = index - 0 + 1
				elif total - target in lookup:
					dp[index] = min(index - lookup[total - target] + 1, dp[index - 1])
				else:
					dp[index] = dp[index - 1]
				lookup[total] = index + 1
			return dp
		forward = getMinSub(arr, target)
		backward = getMinSub(arr[::-1], target)[::-1]
		minresult = float('inf')
		for i in range(1, len(arr)):
			minresult = min(minresult, forward[i - 1] + backward[i])
		return minresult if minresult != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix = {0: -1}
		best_till = [math.inf] * len(arr)
		ans = best = math.inf
		for (i, curr) in enumerate(itertools.accumulate(arr)):
			if curr - target in prefix:
				end = prefix[curr - target]
				if end > -1:
					ans = min(ans, i - end + best_till[end])
				best = min(best, i - end)
			best_till[i] = best
			prefix[curr] = i
		return -1 if ans == math.inf else ans


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		(prefix, suffix) = ([float('inf')] * len(arr), [float('inf')] * len(arr))
		(curSum, l) = (0, 0)
		for r in range(1, len(arr)):
			prefix[r] = prefix[r - 1]
			curSum += arr[r - 1]
			while curSum >= target:
				if curSum == target:
					prefix[r] = min(prefix[r], r - l)
				curSum -= arr[l]
				l += 1
		(curSum, r) = (0, len(arr))
		for l in range(len(arr) - 1, 0, -1):
			if l < len(arr) - 1:
				suffix[l] = suffix[l + 1]
			curSum += arr[l]
			while curSum >= target:
				if curSum == target:
					suffix[l] = min(suffix[l], r - l)
				curSum -= arr[r - 1]
				r -= 1
		res = len(arr) + 1
		for i in range(1, len(arr) - 1):
			res = min(res, prefix[i] + suffix[i])
		return res if res <= len(arr) else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		left_presum = {0: 0}
		left_dp = [float('inf')] * (n + 1)
		total = 0
		for i in range(1, n + 1):
			total += arr[i - 1]
			if total - target in left_presum:
				left_dp[i] = min(i - left_presum[total - target], left_dp[i - 1])
			else:
				left_dp[i] = left_dp[i - 1]
			left_presum[total] = i
		total = 0
		right_presum = {0: n}
		right_dp = [float('inf')] * (n + 1)
		for i in range(n - 1, -1, -1):
			total += arr[i]
			if total - target in right_presum:
				right_dp[i] = min(right_dp[i + 1], right_presum[total - target] - i)
			else:
				right_dp[i] = right_dp[i + 1]
			right_presum[total] = i
		print(right_dp)
		ans = float('inf')
		for i in range(1, n):
			if left_dp[i] == float('inf') or right_dp[i] == float('inf'):
				continue
			ans = min(ans, left_dp[i] + right_dp[i])
		return -1 if ans == float('inf') else ans


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)

		def get_min(arr):
			min_left = [float('inf')] * n
			window = 0
			l = 0
			for r in range(n):
				window += arr[r]
				while window > target:
					window -= arr[l]
					l += 1
				if window == target:
					min_left[r] = r - l + 1
				if r > 0:
					min_left[r] = min(min_left[r], min_left[r - 1])
			return min_left
		min_left = get_min(arr)
		min_right = get_min(arr[::-1])[::-1]
		best = float('inf')
		for i in range(1, n):
			best = min(best, min_left[i - 1] + min_right[i])
		return best if best < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr, target):
		result = inf = 2 ** 31 - 1
		i = window = count = 0
		preMin = [(-1, inf)]
		for (j, num) in enumerate(arr):
			window += num
			while window > target:
				window -= arr[i]
				i += 1
			if window == target:
				curr = j - i + 1
				n = 0
				for (index, length) in preMin[::-1]:
					if index <= i - 1:
						n = length
						break
				if result > curr + n:
					result = curr + n
				if curr < preMin[-1][-1]:
					preMin.append((j, curr))
		return result if result < inf else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		record = collections.defaultdict()
		record[0] = 0
		l1 = l2 = float('Inf')
		tmp_sum = 0
		res = float('Inf')
		dp = [float('Inf') for _ in range(len(arr) + 1)]
		for i in range(len(arr)):
			tmp_sum += arr[i]
			if tmp_sum - target in record:
				dp[i + 1] = i - record[tmp_sum - target] + 1
				res = min(res, dp[i + 1] + dp[record[tmp_sum - target]])
			record[tmp_sum] = i + 1
			dp[i + 1] = min(dp[i + 1], dp[i])
		return res if res < float('Inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		(pre_index, curr_sum) = (0, 0)
		f = [100001] * (len(arr) + 1)
		ans = 100001
		for (index, a) in enumerate(arr):
			curr_sum += a
			while curr_sum > target:
				curr_sum -= arr[pre_index]
				pre_index += 1
			if curr_sum == target:
				ans = min(f[pre_index] + index + 1 - pre_index, ans)
				f[index + 1] = min(f[index], index + 1 - pre_index)
			else:
				f[index + 1] = f[index]
		return -1 if ans >= 100001 else ans


import numpy as np

class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		cumsum = np.cumsum(arr)
		h2idx = {}
		print(cumsum)
		minSum = []
		for (idx, c) in enumerate(cumsum):
			if c == target:
				minSum.append(idx + 1)
			if c - target in h2idx:
				minSum.append(idx - h2idx[c - target])
			h2idx[c] = idx
		if len(minSum) < 2:
			return -1
		return sum(list(sorted(minSum))[:2])

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix = {0: -1}
		best_till = [math.inf] * len(arr)
		ans = best = math.inf
		for (i, curr) in enumerate(itertools.accumulate(arr)):
			if curr - target in prefix:
				end = prefix[curr - target]
				if end > -1:
					ans = min(ans, i - end + best_till[end])
				best = min(best, i - end)
			best_till[i] = best
			prefix[curr] = i
		return -1 if ans == math.inf else ans

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		cumsum = np.cumsum(arr)
		h2idx = {}
		INF = math.inf
		best_at_i = [INF] * len(arr)
		best = INF
		for (idx, c) in enumerate(cumsum):
			if c == target:
				best_at_i[idx] = min(best_at_i[idx - 1], idx + 1)
			if c - target in h2idx:
				left = h2idx[c - target]
				best = min(best, best_at_i[left] + idx - left)
				best_at_i[idx] = min(best_at_i[left], idx - left)
			h2idx[c] = idx
			best_at_i[idx] = min(best_at_i[idx - 1], best_at_i[idx])
		return best if best != INF else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		sumArr = []
		sumMap = {}
		sumMap[0] = -1
		for i in range(len(arr)):
			sumArr.append(arr[i] + (sumArr[i - 1] if i - 1 > -1 else 0))
			sumMap[sumArr[i]] = i
		res = math.inf
		dp = [math.inf for i in range(len(arr))]
		for i in range(0, len(arr)):
			if sumMap.get(sumArr[i] - target) != None:
				dp[i] = min(i - sumMap[sumArr[i] - target], dp[i - 1] if i > 0 else math.inf)
			else:
				dp[i] = dp[i - 1] if i > 0 else math.inf
		print(dp)
		for i in range(len(arr) - 1, -1, -1):
			if sumMap.get(sumArr[i] - target) != None:
				j = sumMap.get(sumArr[i] - target)
				print(j)
				l1 = i - j
				if j > -1 and dp[j] != math.inf:
					res = min(res, l1 + dp[j])
		return -1 if res == math.inf else res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		acc = dict()
		acc[-1] = 0
		for i in range(0, n):
			acc[i] = acc[i - 1] + arr[i]
		best_to = [n + 1 for _ in range(n)]
		best_from = dict()
		min_total = n + 1
		s_left = 0
		for i in range(n):
			if acc[i] - acc[s_left - 1] == target:
				best_to[i] = i - s_left + 1
				best_from[s_left] = i - s_left + 1
			elif acc[i] - acc[s_left - 1] > target:
				while s_left < i:
					s_left += 1
					if acc[i] - acc[s_left - 1] < target:
						break
					if acc[i] - acc[s_left - 1] == target:
						best_to[i] = i - s_left + 1
						best_from[s_left] = i - s_left + 1
						break
		for i in range(1, n):
			best_to[i] = min(best_to[i], best_to[i - 1])
		for i in range(n - 1):
			if best_to[i] > n:
				continue
			if i + 1 in best_from:
				min_total = min(min_total, best_to[i] + best_from[i + 1])
		if min_total > n:
			return -1
		return min_total


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		lengths = [len(arr) + 1] * (len(arr) + 1)
		i = 0
		j = 0
		s = 0
		min_two_sum = len(arr) + 1
		while j <= len(arr):
			if s < target:
				if j == len(arr):
					break
				if j > 0:
					lengths[j] = lengths[j - 1]
				s += arr[j]
				j += 1
			elif s > target:
				s -= arr[i]
				i += 1
			else:
				lengths[j] = min(lengths[j - 1], j - i)
				min_two_sum = min(min_two_sum, lengths[i] + j - i)
				if j == len(arr):
					break
				s += arr[j]
				j += 1
		if min_two_sum > len(arr):
			min_two_sum = -1
		return min_two_sum


from collections import defaultdict

class Solution:

	def getSubArray(self, array, target):
		dic = defaultdict(int)
		minSub = [float('inf')] * len(array)
		currentSum = 0
		for (i, num) in enumerate(array):
			currentSum += num
			if currentSum == target:
				minSub[i] = i - 0 + 1
			elif currentSum - target in dic:
				minSub[i] = i - dic[currentSum - target]
			minSub[i] = min(minSub[i - 1], minSub[i])
			dic[currentSum] = i
		return minSub

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		result = float('inf')
		leftMinSub = self.getSubArray(arr, target)
		rightMinSub = self.getSubArray(arr[::-1], target)[::-1]
		for i in range(1, n):
			result = min(result, leftMinSub[i - 1] + rightMinSub[i])
		if result == float('inf'):
			return -1
		else:
			return result


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix = {0: -1}
		best_sofar_arr = [math.inf]
		best_sofar = math.inf
		curr_best = math.inf
		ans = math.inf
		new_ans = math.inf
		for (i, curr) in enumerate(itertools.accumulate(arr)):
			prefix[curr] = i
			if curr - target in prefix:
				curr_best = i - prefix[curr - target]
				best_sofar = min(best_sofar, curr_best)
				best_sofar_arr.append(best_sofar)
				if i > 0:
					new_ans = curr_best + best_sofar_arr[prefix[curr - target] + 1]
				ans = min(new_ans, ans)
			else:
				best_sofar_arr.append(best_sofar)
		return -1 if ans == math.inf else ans


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		sums = {0: -1}
		prefix = 0
		dp = [math.inf for _ in range(len(arr) + 1)]
		ans = math.inf
		for (idx, num) in enumerate(arr):
			prefix += num
			dp[idx + 1] = min(dp[idx + 1], dp[idx])
			if prefix - target in sums:
				ans = min(ans, idx - sums[prefix - target] + dp[sums[prefix - target] + 1])
				dp[idx + 1] = min(dp[idx + 1], idx - sums[prefix - target])
			sums[prefix] = idx
		return ans if ans != math.inf else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		run = [0, arr[0]]
		h = {0: 0, arr[0]: 1}
		prefix = [len(arr)]
		for i in range(1, len(arr)):
			if run[i] - target in h:
				prefix.append(min(prefix[-1], i - h[run[i] - target]))
			else:
				prefix.append(prefix[-1])
			run.append(run[-1] + arr[i])
			h[run[-1]] = i + 1
		suffix = [len(arr) for i in range(len(arr))]
		if arr[-1] == target:
			suffix[-1] = 1
		for i in range(len(arr) - 2, -1, -1):
			if run[i] + target in h:
				suffix[i] = min(suffix[i + 1], h[run[i] + target] - i)
			else:
				suffix[i] = suffix[i + 1]
		res = len(arr) + 1
		for i in range(len(arr)):
			if not (prefix[i] == len(arr) or suffix[i] == len(arr)):
				res = min(res, prefix[i] + suffix[i])
		if res == len(arr) + 1:
			return -1
		return res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		INF = len(arr) + 1
		best_idx = [INF] * len(arr)
		best = INF
		csum = 0
		left = 0
		for right in range(len(arr)):
			csum += arr[right]
			while csum > target and left <= right:
				csum -= arr[left]
				left += 1
			if csum == target:
				best = min(best, best_idx[left - 1] + right - left + 1)
				best_idx[right] = min(best_idx[right - 1], right - left + 1)
			else:
				best_idx[right] = best_idx[right - 1]
		if INF == best:
			return -1
		return best


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		N = len(arr)
		prefix = [N + 1] * N
		suffix = [N + 1] * N
		presum = dict()
		total = 0
		presum[0] = -1
		for i in range(N):
			total += arr[i]
			presum[total] = i
		prefix[0] = N + 1
		total = 0
		for i in range(0, N):
			total += arr[i]
			t = N + 1
			xx = total - target
			if xx in presum:
				t = i - presum[xx]
			prefix[i] = min(prefix[i - 1], t)
		sufsum = dict()
		total = 0
		sufsum[0] = N
		for i in range(N - 1, -1, -1):
			total += arr[i]
			sufsum[total] = i
		total = 0
		if arr[-1] == target:
			suffix[-1] = 1
		total = arr[-1]
		for i in range(N - 2, -1, -1):
			total += arr[i]
			t = N + 1
			xx = total - target
			if xx in sufsum:
				t = sufsum[xx] - i
			suffix[i] = min(suffix[i + 1], t)
		rtv = N + 1
		for i in range(N - 1):
			cur = prefix[i] + suffix[i + 1]
			rtv = min(rtv, cur)
		if rtv > N:
			return -1
		return rtv


import collections

class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:

		def get_sub_arrays(arr):
			lookup = collections.defaultdict(int)
			running_sum = 0
			dp = [float('inf')] * len(arr)
			for (i, num) in enumerate(arr):
				running_sum += num
				if running_sum == target:
					dp[i] = i - 0 + 1
				elif running_sum - target in lookup:
					dp[i] = i - lookup[running_sum - target] + 1
				lookup[running_sum] = i + 1
				dp[i] = min(dp[i - 1], dp[i])
			return dp
		dp_left = get_sub_arrays(arr)
		dp_right = get_sub_arrays(arr[::-1])[::-1]
		ans = float('inf')
		for i in range(1, len(arr)):
			ans = min(ans, dp_left[i - 1] + dp_right[i])
		return ans if ans != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr, target):
		result = inf = 2 ** 31 - 1
		i = window = count = 0
		preMin = deque([(-1, inf)])
		for (j, num) in enumerate(arr):
			window += num
			while window > target:
				window -= arr[i]
				i += 1
			while len(preMin) >= 2 and preMin[1][0] <= i - 1:
				preMin.popleft()
			if window == target:
				curr = j - i + 1
				n = preMin[0][1]
				if result > curr + n:
					result = curr + n
				if curr < preMin[-1][-1]:
					preMin.append((j, curr))
				if curr == 1:
					count += 1
				if count == 2:
					return 2
		return result if result < inf else -1


class Solution:

	def minSumOfLengths(self, arr, target):
		result = inf = 2 ** 31 - 1
		i = window = 0
		premin = [inf] * len(arr)
		for j in range(len(arr)):
			window += arr[j]
			while window > target:
				window -= arr[i]
				i += 1
			if window == target:
				curr = j - i + 1
				if result > curr + premin[i - 1]:
					result = curr + premin[i - 1]
				premin[j] = curr if curr < premin[j - 1] else premin[j - 1]
			else:
				premin[j] = premin[j - 1]
		return result if result < inf else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		result = float('inf')
		leftmin = self.getMinLen(arr, target, True)
		rightmin = self.getMinLen(arr, target, False)
		for i in range(0, len(arr) - 1):
			result = min(result, leftmin[i] + rightmin[i + 1])
		return result if result != float('inf') else -1

	def getMinLen(self, arr, target, l2r):
		if not l2r:
			arr = arr[::-1]
		memo = {0: 0}
		result = [float('inf')] * len(arr)
		curSum = 0
		for (i, num) in enumerate(arr):
			if i > 0:
				result[i] = result[i - 1]
			curSum += num
			if curSum - target in memo:
				curLen = i - memo[curSum - target] + 1
				result[i] = min(result[i], curLen)
			memo[curSum] = i + 1
		if not l2r:
			result = result[::-1]
		return result


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		prefix = [float('INF')] * (n + 1)
		suffix = [float('INF')] * (n + 1)
		tmp = 0
		start = 0
		for i in range(n):
			if arr[i] == target:
				prefix[i + 1] = 1
			elif tmp + arr[i] < target:
				tmp += arr[i]
			else:
				tmp += arr[i]
				while tmp > target and start < i:
					tmp -= arr[start]
					start += 1
				if tmp == target:
					prefix[i + 1] = i - start + 1
			prefix[i + 1] = min(prefix[i + 1], prefix[i])
		tmp = 0
		start = -1
		for i in range(-1, -n - 1, -1):
			if arr[i] == target:
				suffix[i] = 1
			elif tmp + arr[i] < target:
				tmp += arr[i]
			else:
				tmp += arr[i]
				while tmp > target and start > i:
					tmp -= arr[start]
					start -= 1
				if tmp == target:
					suffix[i] = start - i + 1
			suffix[i] = min(suffix[i], suffix[i + 1])
		min_val = float('INF')
		for i in range(n):
			min_val = min(min_val, prefix[i] + suffix[i + 1])
		return min_val if min_val != float('INF') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		dp = [len(arr) + 1] * len(arr)
		table = {0: -1}
		s = 0
		min_sum = len(arr) + 1
		for i in range(len(arr)):
			s += arr[i]
			if i > 0:
				dp[i] = dp[i - 1]
			if s - target in table:
				length = i - table[s - target]
				dp[i] = min(dp[i], length)
				if length <= i:
					min_sum = min(min_sum, length + dp[i - length])
			table[s] = i
		if min_sum == len(arr) + 1:
			return -1
		else:
			return min_sum


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix = {0: -1}
		current = 0
		queue = []
		for i in range(len(arr)):
			current += arr[i]
			prefix[current] = i
			if not prefix.get(current - target) is None:
				if len(queue) == 0 or prefix[current - target] + 1 > queue[-1][0]:
					queue.append((prefix[current - target] + 1, i))
		if len(queue) < 2:
			return -1
		min_q = []
		current = len(arr)
		for i in range(len(queue) - 1, -1, -1):
			current = min(current, queue[i][1] - queue[i][0] + 1)
			min_q.append(current)
		min_q = min_q[::-1]
		pointer1 = 0
		pointer2 = 1
		res = -1
		while pointer2 < len(queue):
			if queue[pointer2][0] <= queue[pointer1][1]:
				pointer2 += 1
				continue
			if res < 0:
				res = queue[pointer1][1] - queue[pointer1][0] + 1 + min_q[pointer2]
			else:
				res = min(res, queue[pointer1][1] - queue[pointer1][0] + 1 + min_q[pointer2])
			pointer1 += 1
		return res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		l = r = 0
		s = arr[l]
		res = []
		while r < len(arr):
			if s == target:
				ln = r - l + 1
				res.append((ln, l, r))
			if s <= target:
				r += 1
				if r < len(arr):
					s += arr[r]
			else:
				l += 1
				s -= arr[l - 1]
				if l > r:
					r += 1
					if r < len(arr):
						s += arr[r]
		msl = [math.inf] * len(arr)
		msr = [math.inf] * len(arr)
		mi = math.inf
		resi = -1
		for i in range(len(arr)):
			if resi + 1 < len(res) and res[resi + 1][2] == i:
				resi += 1
				mi = min(mi, res[resi][0])
			msl[i] = mi
		mi = math.inf
		resi = len(res)
		for i in range(len(arr) - 1, -1, -1):
			if resi - 1 >= 0 and res[resi - 1][1] == i:
				resi -= 1
				mi = min(mi, res[resi][0])
			msr[i] = mi
		mn = math.inf
		for i in range(len(arr) - 1):
			mn = min(mn, msl[i] + msr[i + 1])
		if mn == math.inf:
			return -1
		return mn


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		min_range = None
		left = self.get_list(arr, target)
		right = list(reversed(self.get_list(list(reversed(arr)), target)))
		print(left)
		print(right)
		min_length = None
		for i in range(len(arr) - 1):
			if left[i] != -1 and right[i + 1] != -1:
				if not min_length:
					min_length = left[i] + right[i + 1]
				else:
					min_length = min(left[i] + right[i + 1], min_length)
		return -1 if not min_length else min_length

	def get_list(self, arr, target):
		prefix_d = dict()
		prefix_d[0] = -1
		min_range_list = []
		current_min = -1
		current = 0
		for i in range(len(arr)):
			current += arr[i]
			if current - target in prefix_d:
				prev_idx = prefix_d[current - target]
				dis = i - prev_idx
				if current_min == -1:
					current_min = dis
				else:
					current_min = min(current_min, dis)
			min_range_list.append(current_min)
			prefix_d[current] = i
		return min_range_list


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		MAX = float('inf')
		n = len(arr) + 1
		best_till = [MAX for i in range(n + 1)]
		presum = 0
		maps = {}
		maps[0] = -1
		ans = best = MAX
		for (i, v) in enumerate(arr):
			presum += v
			key = presum - target
			if key in maps:
				left_idx = maps[key]
				curr_len = i - left_idx
				best = min(best, curr_len)
				if left_idx > -1:
					first_len = best_till[left_idx]
					ans = min(ans, first_len + curr_len)
			best_till[i] = best
			maps[presum] = i
		if ans == MAX:
			return -1
		return ans


INF = int(1000000000.0)

class Solution:

	def shortest_subarrays(self, a, target):
		cum = [0]
		for x in a:
			cum.append(cum[-1] + x)
		hist = {0: 0}
		ret = [INF]
		for i in range(1, len(cum)):
			ci = cum[i]
			begin = hist.get(ci - target, -1)
			if begin >= 0:
				ret.append(min(i - begin, ret[-1]))
			else:
				ret.append(ret[-1])
			hist[ci] = i
		return ret

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		forward = self.shortest_subarrays(arr, target)
		backward = self.shortest_subarrays(reversed(arr), target)
		ret = INF
		for i in range(1, len(arr) - 1 + 1):
			ret = min(ret, forward[i] + backward[len(arr) - i])
		if ret >= INF:
			return -1
		return ret


from typing import List
import math
import sys

class Solution:

	def __init__(self):
		self.preceeding_soln_lens = []

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		self.preceeding_soln_lens = [sys.maxsize] * len(arr)
		min_len_sum = sys.maxsize
		buffer = []
		buffer_sum = 0
		buffer_len = 0
		i = 0
		while i < len(arr):
			buffer_sum += arr[i]
			buffer_len += 1
			buffer.append(i)
			sub_array_end_idx = buffer[-1]
			if buffer_sum < target:
				self.preceeding_soln_lens[sub_array_end_idx] = self.preceeding_soln_lens[sub_array_end_idx - 1]
			while buffer_sum >= target:
				popped_idx = buffer.pop(0)
				if buffer_sum == target:
					self.preceeding_soln_lens[sub_array_end_idx] = min(buffer_len, self.preceeding_soln_lens[sub_array_end_idx - 1])
					if popped_idx > 0:
						non_overlapping_previous_soln_idx = popped_idx - 1
						min_len_sum = min(min_len_sum, self.preceeding_soln_lens[non_overlapping_previous_soln_idx] + buffer_len)
				else:
					self.preceeding_soln_lens[sub_array_end_idx] = self.preceeding_soln_lens[sub_array_end_idx - 1]
				buffer_len -= 1
				buffer_sum -= arr[popped_idx]
			i += 1
		if min_len_sum == sys.maxsize:
			return -1
		return min_len_sum


from typing import List
import heapq
import math
import sys

class Solution:

	def __init__(self):
		self.preceeding_soln_lens = []
		self.segment_tree = []

	def has_overlap(self, rng, list_of_ranges):
		(s, e) = rng
		if len(list_of_ranges):
			(os, oe) = list_of_ranges[-1]
			if e < os or oe < s:
				pass
			else:
				return True
		return False

	def find_min(self, s, e):
		min_val = sys.maxsize
		for i in range(s, e):
			if self.preceeding_soln_lens[i]:
				min_val = min(min_val, self.preceeding_soln_lens[i])
		if min_val == sys.maxsize:
			return None
		return min_val

	def n2_find(self, i, lengths):
		len_one = self.find_min(0, i)
		if len_one:
			len_two = self.find_min(i + len_one - 1, len(self.preceeding_soln_lens))
			if len_two:
				heapq.heappush(lengths, len_one + len_two)

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		self.preceeding_soln_lens = [sys.maxsize] * len(arr)
		min_len_sum = sys.maxsize
		buffer = []
		buffer_sum = 0
		buffer_len = 0
		i = 0
		while i < len(arr):
			buffer_sum += arr[i]
			buffer_len += 1
			buffer.append(i)
			sub_array_end_idx = buffer[-1]
			if buffer_sum < target:
				self.preceeding_soln_lens[sub_array_end_idx] = self.preceeding_soln_lens[sub_array_end_idx - 1]
			while buffer_sum >= target:
				popped_idx = buffer.pop(0)
				if buffer_sum == target:
					self.preceeding_soln_lens[sub_array_end_idx] = min(buffer_len, self.preceeding_soln_lens[sub_array_end_idx - 1])
					if popped_idx > 0:
						non_overlapping_previous_soln_idx = popped_idx - 1
						min_len_sum = min(min_len_sum, self.preceeding_soln_lens[non_overlapping_previous_soln_idx] + buffer_len)
				else:
					self.preceeding_soln_lens[sub_array_end_idx] = self.preceeding_soln_lens[sub_array_end_idx - 1]
				buffer_len -= 1
				buffer_sum -= arr[popped_idx]
			i += 1
		if min_len_sum == sys.maxsize:
			return -1
		return min_len_sum


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix_sum = {0: -1}
		cur_sum = 0
		for (i, val) in enumerate(arr):
			cur_sum += val
			prefix_sum[cur_sum] = i
		left_min_len = float('inf')
		ans = float('inf')
		cur_sum = 0
		for (i, val) in enumerate(arr):
			cur_sum += val
			if cur_sum - target in prefix_sum:
				left_min_len = min(left_min_len, i - prefix_sum[cur_sum - target])
			if cur_sum + target in prefix_sum:
				ans = min(ans, left_min_len + prefix_sum[cur_sum + target] - i)
		return ans if ans < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		left_min = self.getMinArr(arr, target, True)
		right_min = self.getMinArr(arr, target, False)
		result = sys.maxsize
		for i in range(0, len(arr) - 1):
			if max(left_min[i], right_min[i + 1]) != sys.maxsize:
				result = min(left_min[i] + right_min[i + 1], result)
		return result if result < sys.maxsize else -1

	def getMinArr(self, arr, target, right):
		result = [sys.maxsize] * len(arr)
		current_sum = 0
		num_map = {0: 0}
		nums = arr if right else arr[::-1]
		for (i, num) in enumerate(nums):
			if i > 0:
				result[i] = result[i - 1]
			current_sum += num
			if current_sum - target in num_map:
				current_len = i - num_map[current_sum - target] + 1
				result[i] = min(result[i], current_len)
			num_map[current_sum] = i + 1
		if not right:
			result.reverse()
		return result


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)

		def aux(arr):
			h = {0: 0}
			preSum = 0
			left = [n + 1 for i in range(n)]
			for i in range(1, n + 1):
				preSum = preSum + arr[i - 1]
				h[preSum] = i
				if preSum - target in h:
					left[i - 1] = i - h[preSum - target]
				if i > 1:
					left[i - 1] = min(left[i - 2], left[i - 1])
			return left
		left = aux(arr)
		arr.reverse()
		right = aux(arr)
		ans = n + 1
		for i in range(n - 1):
			ans = min(ans, left[i] + right[n - 1 - (i + 1)])
		return ans if ans < n + 1 else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:

		def get_shortest(array):
			shortest = [float('infinity') for _ in range(len(arr))]
			prefix_pos = {}
			prefix_sum = 0
			for i in range(len(array)):
				prefix_sum += array[i]
				if prefix_sum == target:
					if i == 0:
						shortest[i] = i + 1
					else:
						shortest[i] = min(shortest[i - 1], i + 1)
				elif prefix_sum - target in prefix_pos:
					shortest[i] = i - prefix_pos[prefix_sum - target] + 1
				shortest[i] = min(shortest[i - 1], shortest[i])
				prefix_pos[prefix_sum] = i + 1
			return shortest
		left = get_shortest(arr)
		right = get_shortest(arr[::-1])[::-1]
		res = float('infinity')
		for i in range(len(left) - 1):
			res = min(res, left[i] + right[i + 1])
		if res == float('infinity'):
			return -1
		return res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		left_sub_array = [len(arr)] * len(arr)
		(sub_sum, next_index) = (0, 0)
		for index in range(len(arr)):
			while sub_sum < target and next_index < len(arr):
				sub_sum += arr[next_index]
				if sub_sum > target:
					sub_sum -= arr[next_index]
					break
				else:
					if sub_sum == target:
						left_sub_array[next_index] = next_index - index + 1
					next_index += 1
			sub_sum -= arr[index]
			left_sub_array[index] = min(left_sub_array[index], left_sub_array[index - 1])
		r_arr = arr[::-1]
		right_sub_array = [len(r_arr)] * len(r_arr)
		(sub_sum, next_index) = (0, 0)
		for index in range(len(r_arr)):
			while sub_sum < target and next_index < len(r_arr):
				sub_sum += r_arr[next_index]
				if sub_sum > target:
					sub_sum -= r_arr[next_index]
					break
				else:
					if sub_sum == target:
						right_sub_array[next_index] = next_index - index + 1
					next_index += 1
			sub_sum -= r_arr[index]
			right_sub_array[index] = min(right_sub_array[index], right_sub_array[index - 1])
		right_sub_array = right_sub_array[::-1]
		min_length = 2 * len(arr)
		for (index, val) in enumerate(left_sub_array[:-1]):
			min_length = min(min_length, val + right_sub_array[index + 1])
		if min_length > len(arr):
			return -1
		else:
			return min_length


class Solution:

	def getArraysx(self, arr, target):
		leftSizes = {}
		rightSizes = {}
		posleft = 0
		posright = 0
		currSum = 0
		while posright < len(arr):
			currSum += arr[posright]
			if currSum == target:
				rightList = rightSizes.get(posleft, [])
				rightList.append(posright - posleft + 1)
				rightSizes[posleft] = rightList
				if posright + 1 < len(arr):
					leftList = leftSizes.get(posright + 1, [])
					leftList.append(posright - posleft + 1)
					leftSizes[posright + 1] = leftList
				posright += 1
				currSum -= arr[posleft]
				posleft += 1
			elif currSum > target:
				currSum = currSum - arr[posright] - arr[posleft]
				posleft += 1
			else:
				posright += 1
		leftArray = [0] * len(arr)
		fullList = []
		for i in range(len(arr)):
			additional = leftSizes.get(i, [])
			fullList.extend(additional)
			if len(fullList) > 0:
				leftArray[i] = min(fullList)
			else:
				leftArray[i] = -1
		rightArray = [0] * len(arr)
		fullList = []
		for j in range(len(arr) - 1, -1, -1):
			additional = rightSizes.get(j, [])
			fullList.extend(additional)
			if len(fullList) > 0:
				rightArray[j] = min(fullList)
			else:
				rightArray[j] = -1
		return (leftArray, rightArray)

	def updateArrays(self, leftSizes, rightSizes, posleft, posright, maxvalue):
		value = rightSizes.get(posleft, maxvalue)
		rightSizes[posleft] = min(value, posright - posleft + 1)
		if posright + 1 < maxvalue:
			value = leftSizes.get(posright + 1, maxvalue)
			leftSizes[posright + 1] = min(value, posright - posleft + 1)

	def getArrays(self, arr, target):
		leftArray = [0] * len(arr)
		rightArray = [0] * len(arr)
		leftSizes = {}
		rightSizes = {}
		posleft = 0
		posright = 0
		currSum = 0
		while posright < len(arr):
			currSum += arr[posright]
			if currSum == target:
				self.updateArrays(leftSizes, rightSizes, posleft, posright, len(arr))
				posright += 1
				currSum -= arr[posleft]
				posleft += 1
			elif currSum > target:
				currSum = currSum - arr[posright] - arr[posleft]
				posleft += 1
			else:
				posright += 1
		leftArray = [len(arr)] * len(arr)
		for i in range(1, len(arr)):
			minValue = leftSizes.get(i, len(arr))
			leftArray[i] = min(minValue, leftArray[i - 1])
		rightArray = [len(arr)] * len(arr)
		for j in range(len(arr) - 1, -1, -1):
			minValue = rightSizes.get(j, len(arr))
			if j == len(arr) - 1:
				rightArray[j] = minValue
			else:
				rightArray[j] = min(minValue, rightArray[j + 1])
		return (leftArray, rightArray)

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		(leftArray, rightArray) = self.getArrays(arr, target)
		minSum = 2 * len(arr)
		for i in range(1, len(arr)):
			if leftArray[i] < len(arr):
				leftSize = leftArray[i]
			else:
				continue
			if rightArray[i] < len(arr):
				rightSize = rightArray[i]
			else:
				continue
			minSum = min(minSum, leftSize + rightSize)
		if minSum == 2 * len(arr):
			minSum = -1
		return minSum

	def minSumOfLengthsx(self, arr: List[int], target: int) -> int:
		posleft = 0
		posright = 0
		lengths = []
		currSum = 0
		while posright < len(arr):
			currSum += arr[posright]
			if currSum == target:
				lengths.append(posright - posleft + 1)
				posright += 1
				posleft = posright
				currSum = 0
			elif currSum > target:
				currSum = currSum - arr[posright] - arr[posleft]
				posleft += 1
			else:
				posright += 1
		print(lengths)
		if len(lengths) < 2:
			return -1
		lengths.sort()
		return sum(lengths[0:2])


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:

		def prefix_sum(arr):
			lookup = {}
			dp = [float('inf')] * len(arr)
			cumsum = 0
			for (i, num) in enumerate(arr):
				cumsum += num
				if cumsum == target:
					dp[i] = i - 0 + 1
				elif cumsum - target in lookup:
					dp[i] = i - lookup[cumsum - target]
				lookup[cumsum] = i
				dp[i] = min(dp[i - 1], dp[i])
			return dp
		prefix = prefix_sum(arr)
		suffix = prefix_sum(arr[::-1])[::-1]
		ans = float('inf')
		for i in range(1, len(arr)):
			ans = min(ans, prefix[i - 1] + suffix[i])
		return ans if ans != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		if len(arr) < 2:
			return -1
		n = len(arr)
		curSum = 0
		prefixSum = {0: -1}
		dp = [float('inf')] * n
		ans = float('inf')
		for i in range(n):
			curSum += arr[i]
			if curSum - target in prefixSum:
				j = prefixSum[curSum - target] + 1
				ans = min(ans, i - j + 1 + dp[j - 1])
				dp[i] = min(dp[i - 1], i - j + 1)
			else:
				dp[i] = dp[i - 1]
			prefixSum[curSum] = i
		return ans if ans < float('inf') else -1


class Solution:

	def getMinArr(self, arr, target, right=False):
		pre_sum = 0
		res = [float('inf') for i in range(len(arr))]
		sum_dict = {0: 0}
		if right:
			arr = arr[::-1]
		for (i, num) in enumerate(arr):
			pre_sum += num
			if i > 0:
				res[i] = res[i - 1]
			if pre_sum - target in sum_dict:
				cur_len = i - sum_dict[pre_sum - target] + 1
				res[i] = min(res[i], cur_len)
			sum_dict[pre_sum] = i + 1
		if right:
			res.reverse()
		return res

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		left_min = self.getMinArr(arr, target)
		right_min = self.getMinArr(arr, target, True)
		min_len = float('inf')
		for i in range(len(arr) - 1):
			min_len = min(min_len, left_min[i] + right_min[i + 1])
		if min_len == float('inf'):
			return -1
		return min_len


import sys

class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		table = {0: -1}
		cursum = 0
		dp1 = [sys.maxsize for i in range(len(arr))]
		for i in range(len(arr)):
			if i > 0:
				dp1[i] = dp1[i - 1]
			cursum += arr[i]
			if cursum - target in list(table.keys()):
				dp1[i] = min(dp1[i], i - table[cursum - target])
			table[cursum] = i
		table = {0: len(arr)}
		cursum = 0
		dp2 = [sys.maxsize for i in range(len(arr))]
		for i in range(len(arr) - 1, -1, -1):
			if i < len(arr) - 1:
				dp2[i] = dp2[i + 1]
			cursum += arr[i]
			if cursum - target in list(table.keys()):
				dp2[i] = min(dp2[i], table[cursum - target] - i)
			table[cursum] = i
		res = sys.maxsize
		for i in range(len(dp1) - 1):
			if dp1[i] != sys.maxsize and dp2[i + 1] != sys.maxsize:
				res = min(res, dp1[i] + dp2[i + 1])
		if res == sys.maxsize:
			return -1
		else:
			return res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)

		def get_dp(arr):
			dp = []
			ptr = 0
			total = 0
			min_val = float('inf')
			for i in range(n):
				total += arr[i]
				while ptr < i and total > target:
					total -= arr[ptr]
					ptr += 1
				if total == target:
					min_val = min(min_val, i - ptr + 1)
				dp.append(min_val)
			return dp
		dp_left = get_dp(arr)
		dp_right = get_dp(arr[::-1])[::-1]
		min_val = float('inf')
		for i in range(n - 1):
			min_val = min(min_val, dp_left[i] + dp_right[i + 1])
		return min_val if min_val != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix = [0]
		d = {0: -1}
		for i in range(len(arr)):
			prefix.append(arr[i] + prefix[-1])
			d[prefix[-1]] = i
		ans = first = second = float('inf')
		for i in range(len(arr)):
			if prefix[i + 1] - target in d:
				first = min(first, i - d[prefix[i + 1] - target])
			if first < float('inf') and prefix[i + 1] + target in d:
				second = d[prefix[i + 1] + target] - i
				ans = min(ans, first + second)
		return -1 if ans == float('inf') else ans


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		preSum = [0]
		for val in arr:
			preSum.append(preSum[-1] + val)
		sumMap = {}
		preCands = [sys.maxsize] * len(arr)
		sufCands = [sys.maxsize] * len(arr)
		for (i, val) in enumerate(preSum):
			if val - target in sumMap:
				sufCands[sumMap[val - target]] = i - sumMap[val - target]
				preCands[i - 1] = i - sumMap[val - target]
			sumMap[val] = i
		prefixSum = [sys.maxsize] * len(arr)
		suffixSum = [sys.maxsize] * len(arr)
		for (i, val) in enumerate(preCands):
			if i + 1 < len(prefixSum):
				prefixSum[i + 1] = min(preCands[i], prefixSum[i])
		for (i, val) in reversed(list(enumerate(sufCands))):
			if i + 1 < len(suffixSum):
				suffixSum[i] = min(sufCands[i], suffixSum[i + 1])
			else:
				suffixSum[i] = sufCands[i]
		res = sys.maxsize
		for i in range(len(arr)):
			res = min(res, prefixSum[i] + suffixSum[i])
		return res if res != sys.maxsize else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		length = len(arr)
		cumulative = [0] * length
		reverse_cumulative = [0] * length
		s = 0
		sr = 0
		for i in range(length):
			s = s + arr[i]
			cumulative[i] = s
			sr += arr[length - 1 - i]
			reverse_cumulative[i] = sr
		d = {0: -1}
		dr = {0: -1}
		forward_vals = [math.inf] * length
		backward_vals = [math.inf] * length
		best1 = math.inf
		best2 = math.inf
		i = 0
		while i < length:
			d[cumulative[i]] = i
			dr[reverse_cumulative[i]] = i
			if cumulative[i] - target in d:
				l = i - d[cumulative[i] - target]
				best1 = min(best1, l)
			forward_vals[i] = best1
			if reverse_cumulative[i] - target in dr:
				l = i - dr[reverse_cumulative[i] - target]
				best2 = min(best2, l)
			backward_vals[i] = best2
			i += 1
		best1 = math.inf
		for i in range(len(forward_vals) - 1):
			best1 = min(best1, forward_vals[i] + backward_vals[length - 2 - i])
		if best1 == math.inf:
			return -1
		return best1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		sP = 0
		fP = 0
		intervalHeap = []
		sumSoFar = 0
		while fP < len(arr):
			sumSoFar += arr[fP]
			if sumSoFar >= target:
				if sumSoFar == target:
					heapq.heappush(intervalHeap, (fP - sP + 1, sP, fP))
				while sumSoFar >= target:
					sumSoFar -= arr[sP]
					sP += 1
					if sumSoFar == target:
						heapq.heappush(intervalHeap, (fP - sP + 1, sP, fP))
			fP += 1
		if len(intervalHeap) > 1:
			first = heapq.heappop(intervalHeap)
			second = heapq.heappop(intervalHeap)
			if first[2] < second[1] or second[2] < first[1]:
				return first[0] + second[0]
			else:
				while intervalHeap:
					third = heapq.heappop(intervalHeap)
					if third and first[2] < third[1] or third[2] < first[1]:
						return first[0] + third[0]
					elif third and second[2] < third[1] or third[2] < second[1]:
						return second[0] + third[0]
		return -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		lim = len(arr)
		pref = [arr[0]]
		d = dict()
		e = dict()
		d[arr[0]] = [0]
		e[arr[0]] = 1
		for i in range(1, lim):
			pref.append(pref[-1] + arr[i])
			try:
				d[pref[-1]].append(i)
				e[pref[i]] += 1
			except:
				d[pref[-1]] = [i]
				e[pref[i]] = 1
		A = [lim] * lim
		for i in range(0, lim):
			val = target + pref[i] - arr[i]
			if val in d:
				l = 0
				h = e[val] - 1
				mn = lim + 1
				while l <= h:
					m = (l + h) // 2
					if d[val][m] >= i:
						if d[val][m] < mn:
							mn = d[val][m]
						h = m - 1
					else:
						l = m + 1
				if mn != lim + 1:
					A[i] = mn - i + 1
			if arr[i] == target:
				A[i] = 1
		pmn = lim
		p = [lim] * lim
		s = [lim] * lim
		for i in range(0, lim):
			if i + A[i] < lim and p[i + A[i]] > A[i]:
				p[i + A[i]] = A[i]
		smn = lim
		if A[-1] < lim:
			smn = A[-1]
		for i in range(lim - 1, -1, -1):
			if A[i] < smn:
				smn = A[i]
			s[i] = smn
		mn = lim + 1
		for i in range(0, lim):
			if p[i] + s[i] < mn:
				mn = p[i] + s[i]
		if mn >= lim + 1:
			return -1
		return mn


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		prefix_sum = list(accumulate(arr))
		suffix_sum = list(accumulate(arr[::-1]))

		def helper(prefix_sum, n, target):
			dict_x = {0: -1}
			l_1 = [n + 1 for _ in range(n)]
			for i in range(n):
				t1 = prefix_sum[i] - target
				x = n + 1
				if dict_x.get(t1, 'x') != 'x':
					x = i - dict_x[t1]
				l_1[i] = min(x, l_1[i - 1] if i > 0 else n + 1)
				dict_x[prefix_sum[i]] = i
			return l_1
		l = helper(prefix_sum, n, target)
		r = helper(suffix_sum, n, target)[::-1]
		ans = sys.maxsize
		for i in range(n - 1):
			ans = min(ans, l[i] + r[i + 1])
		print(ans)
		return ans if ans <= n else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		smallest = [math.inf] * len(arr)
		q = deque()
		curr_sum = 0
		result = math.inf
		for (i, n) in enumerate(arr):
			curr_sum += n
			q.append(i)
			while curr_sum > target:
				curr_sum -= arr[q.popleft()]
			if curr_sum == target:
				if i == 0:
					smallest[i] = len(q)
				else:
					smallest[i] = min(len(q), smallest[i - 1])
					result = min(result, smallest[q[0] - 1] + len(q))
			else:
				smallest[i] = smallest[i - 1]
		return -1 if result == math.inf else result


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n_arr = len(arr)
		if n_arr == 0:
			return -1

		def get_minlen_ending_before(array: List[int]) -> List[int]:
			n_array = len(array)
			minlen_array = [float('inf')] * n_array
			curr_sum = array[0]
			i = 0
			j = 0
			min_len = float('inf')
			while i < n_array and j < n_array:
				increment_i = False
				increment_j = False
				if curr_sum == target:
					min_len = min(min_len, j - i + 1)
					curr_sum -= array[i]
					increment_i = True
				elif curr_sum < target:
					increment_j = True
					if j < n_array - 1:
						curr_sum += array[j + 1]
				elif curr_sum > target:
					curr_sum -= array[i]
					increment_i = True
				if j < n_array - 1:
					minlen_array[j + 1] = min_len
				if increment_i:
					i += 1
				if increment_j:
					j += 1
				if j < i and i < n_array:
					j = i
					curr_sum = array[i]
			return minlen_array
		prefix = get_minlen_ending_before(arr)
		postfix = get_minlen_ending_before(arr[::-1] + [0])[1:][::-1]
		min_sum = float('inf')
		for i in range(n_arr):
			min_sum = min(min_sum, prefix[i] + postfix[i])
		return min_sum if min_sum < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		su = 0
		s = 0
		min_len = float('inf')
		min_lens = [float('inf') for _ in range(n)]
		ans = float('inf')
		for e in range(n):
			su += arr[e]
			while su > target:
				su -= arr[s]
				s += 1
			if su == target:
				cur_len = e - s + 1
				if s > 0 and min_lens[s - 1] != float('inf'):
					ans = min(ans, cur_len + min_lens[s - 1])
				min_len = min(min_len, cur_len)
			min_lens[e] = min_len
		return -1 if ans >= float('inf') else ans


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		left = list(itertools.accumulate(arr))
		right = list(itertools.accumulate(arr[::-1]))
		right = right[::-1]
		rans = [500000] * len(arr)
		lans = [500000] * len(arr)
		(i, j, n) = (0, 0, len(arr))
		while i < n and j < n:
			sm = left[j] - (left[i - 1] if i else 0)
			while sm > target and i <= j:
				i += 1
				sm = left[j] - (left[i - 1] if i else 0)
			if sm == target:
				lans[j] = min(lans[j], j - i + 1)
			j += 1
		(i, j) = (n - 1, n - 1)
		while i > -1:
			sm = right[i] - (right[j + 1] if j + 1 < n else 0)
			while sm > target and j >= i:
				j -= 1
				sm = right[i] - (right[j + 1] if j + 1 < n else 0)
			if sm == target:
				rans[i] = min(rans[i], j - i + 1)
			i -= 1
		ans = math.inf
		mv = 999999999
		for i in range(n):
			mv = min(mv, lans[i])
			lans[i] = mv
		mv = 212498174
		for i in range(n - 1, -1, -1):
			mv = min(mv, rans[i])
			rans[i] = mv
		for i in range(n - 1):
			ans = min(ans, lans[i] + rans[i + 1])
		return ans if ans < 500000 else -1


from collections import deque
import heapq

class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		shortest = sys.maxsize
		record = {}
		left = 0
		curr_sum = 0
		for right in range(len(arr)):
			curr_sum += arr[right]
			while curr_sum > target and left <= right:
				curr_sum -= arr[left]
				left += 1
			if curr_sum == target:
				curr_len = right - left + 1
				prev_len = record.get(left - 1, sys.maxsize)
				record[right] = min(record.get(right - 1, sys.maxsize), curr_len)
				shortest = min(shortest, curr_len + prev_len)
			else:
				record[right] = record.get(right - 1, sys.maxsize)
		if shortest == sys.maxsize:
			return -1
		return shortest


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		res = [float('inf')] * len(arr)
		ans = float('inf')
		currMin = float('inf')
		i = 0
		s = 0
		for j in range(len(arr)):
			s += arr[j]
			while s > target:
				s -= arr[i]
				i += 1
			if s == target:
				currMin = min(currMin, j - i + 1)
				ans = min(ans, j - i + 1 + res[i - 1])
			res[j] = currMin
		return ans if ans < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		dp = [10000000] * n
		presum = {}
		presum[0] = -1
		s = 0
		bestsofar = 10000000
		ans = 10000000
		for i in range(n):
			s += arr[i]
			if s - target in presum:
				j = presum[s - target]
				bestsofar = min(bestsofar, i - j)
				if j >= 0:
					ans = min(ans, dp[j] + i - j)
			presum[s] = i
			dp[i] = bestsofar
		return ans if ans < 10000000 else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		if not arr:
			return -1

		def getdp(arr):
			dp = [float('inf')] * len(arr)
			summ = 0
			lookup = defaultdict(int)
			for (index, num) in enumerate(arr):
				summ += num
				if summ == target:
					dp[index] = index - 0 + 1
				elif summ - target in lookup:
					dp[index] = min(index - lookup[summ - target] + 1, dp[index - 1])
				else:
					dp[index] = dp[index - 1]
				lookup[summ] = index + 1
			return dp
		dp_left = getdp(arr)
		dp_right = getdp(arr[::-1])[::-1]
		ans = float('inf')
		for i in range(1, len(arr)):
			ans = min(ans, dp_left[i - 1] + dp_right[i])
		return ans if ans != float('inf') else -1


class Solution(object):

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix = {0: -1}
		best_till = [math.inf] * len(arr)
		ans = best = math.inf
		for (i, curr) in enumerate(itertools.accumulate(arr)):
			if curr - target in prefix:
				end = prefix[curr - target]
				if end > -1:
					ans = min(ans, i - end + best_till[end])
				best = min(best, i - end)
			best_till[i] = best
			prefix[curr] = i
		return -1 if ans == math.inf else ans

	def OldminSumOfLengths(self, arr, target):
		(ans, l) = (math.inf, len(arr))
		la = [math.inf] * l
		(p1, p2, s, ml) = (0, 0, arr[0], math.inf)
		while p1 < l and p2 < l:
			action = None
			la[p2] = ml
			curl = p2 - p1 + 1
			if s == target:
				ml = min(ml, curl)
				la[p2] = ml
				if p1 - 1 >= 0:
					ans = min(ans, la[p1 - 1] + curl)
				p2 += 1
				action = 1
			elif s < target:
				p2 += 1
				action = 1
			elif s > target:
				p1 += 1
				action = -1
			if p1 >= l or p2 >= l:
				break
			elif p1 > p2:
				p2 = p1
				s = arr[p1]
			elif action == 1:
				s += arr[p2]
			elif action == -1:
				s -= arr[p1 - 1]
		return -1 if ans == math.inf else ans


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		pref = {0: -1}
		result = best = math.inf
		best_till = [math.inf] * len(arr)
		for (i, curr) in enumerate(itertools.accumulate(arr)):
			diff = curr - target
			if diff in pref:
				left = pref[diff]
				length = i - left
				result = min(result, best_till[left] + length)
				best = min(best, length)
			pref[curr] = i
			best_till[i] = best
		return result if result < math.inf else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		premin = [float('inf')] * len(arr)
		(l, cur, res) = (0, 0, float('inf'))
		for (r, num) in enumerate(arr):
			if r > 0:
				premin[r] = premin[r - 1]
			cur += num
			while cur > target:
				cur -= arr[l]
				l += 1
			if cur == target:
				size = r - l + 1
				if l > 0:
					res = min(res, size + premin[l - 1])
				premin[r] = min(premin[r], size)
		return res if res < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		psum = {0: -1}
		csum = 0
		re = 100001
		dp = [100001] * len(arr)
		best = 100001
		for (i, csum) in enumerate(itertools.accumulate(arr)):
			psum[csum] = i
			if csum - target in psum:
				best = min(best, i - psum[csum - target])
				re = min(re, dp[psum[csum - target]] + i - psum[csum - target])
			dp[i] = best
		if re < 100001:
			return re
		return -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix = {0: -1}
		best_till = [math.inf] * len(arr)
		ans = best = math.inf
		for i in range(1, len(arr)):
			arr[i] += arr[i - 1]
		for (i, cur) in enumerate(arr):
			if cur - target in prefix:
				end = prefix[cur - target]
				if end > -1:
					ans = min(ans, i - end + best_till[end])
				best = min(best, i - end)
			best_till[i] = best
			prefix[cur] = i
		return -1 if ans == math.inf else ans


class Solution:

	def minSumOfLengthsOld(self, arr: List[int], target: int) -> int:
		n = len(arr)
		if n == 1:
			return -1
		i = 0
		j = 0
		sum_ = arr[i]
		interval = []
		while i < n and j < n:
			if sum_ == target:
				interval.append([i, j, j - i + 1])
				sum_ -= arr[i]
				i += 1
				j += 1
				if j < n:
					sum_ += arr[j]
			elif sum_ < target:
				if j < n - 1:
					sum_ += arr[j + 1]
				j += 1
			else:
				sum_ -= arr[i]
				i += 1
		if len(interval) == 0:
			return -1
		interval.sort(key=lambda x: x[2])
		interval_val_sorted = [x for x in interval]
		interval.sort(key=lambda x: x[0])
		print(interval_val_sorted)
		print(interval)
		(i_, j_, l_) = (interval[0][0], interval[0][1], interval[0][2])
		found = False
		for i in range(1, len(interval), 1):
			(i_1, j_1, l_1) = (interval[i][0], interval[i][1], interval[i][2])
			if i_1 >= i_ and i_1 <= j_:
				continue
			if i_ >= i_1 and i_ <= j_1:
				continue
			found = True
			break
		if found == False:
			return -1
		return l_ + l_1

	def findCeil(self, x, starts):
		s = 0
		e = len(starts) - 1
		res = -1
		while s <= e:
			mid = s + (e - s) // 2
			if starts[mid] > x:
				res = mid
				e = mid - 1
			else:
				s = mid + 1
		return res

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		i = 0
		j = 0
		overlaps = list()
		sum_ = 0
		j = 0
		while i < n and j < n:
			sum_ += arr[j]
			while j < n - 1 and sum_ < target:
				j += 1
				sum_ += arr[j]
			if sum_ == target:
				overlaps.append([i, j])
			sum_ -= arr[i]
			sum_ -= arr[j]
			i += 1
		if sum_ == target:
			if i <= n - 1:
				overlaps.append([i, j - 1])
		starting = [x for [x, y] in overlaps]
		length = [y - x + 1 for [x, y] in overlaps]
		l_o = len(length)
		if l_o == 0:
			return -1
		min_arr = [length[-1]]
		s = 1
		min_ = length[-1]
		for i in range(l_o - 2, -1, -1):
			min_ = min(length[i], min_)
			min_arr.append(min_)
		min_length = sys.maxsize
		min_arr = list(reversed(min_arr))
		for overlap in overlaps:
			(s, e) = (overlap[0], overlap[1])
			indi = self.findCeil(e, starting)
			if indi == -1:
				continue
			min_length = min(min_length, e - s + 1 + min_arr[indi])
		if min_length == sys.maxsize:
			return -1
		return min_length


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		left = self.shortestTails(arr, target, False)
		right = self.shortestTails(arr, target, True)
		mn = float('inf')
		for i in range(len(arr) - 1):
			if left[i][0] < float('inf') and right[i + 1][0] < float('inf'):
				mn = min(mn, left[i][0] + right[i + 1][0])
		return mn if mn < float('inf') else -1

	def shortestTails(self, arr, target, reverse):
		end = len(arr) - 1 if reverse else 0
		prefixSumMap = {0: len(arr) if reverse else -1}
		s = 0
		shortestAt = [None] * len(arr)
		shortest = (float('inf'), -1, -1)
		for _ in range(len(arr)):
			s += arr[end]
			diff = s - target
			if diff in prefixSumMap:
				start = prefixSumMap[diff]
				if abs(end - start) < shortest[0]:
					shortest = (abs(end - start), start, end)
			shortestAt[end] = shortest
			prefixSumMap[s] = end
			end = end - 1 if reverse else end + 1
		return shortestAt


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		mp = {}
		sum_list = 0
		mp[0] = -1
		for (i, val) in enumerate(arr):
			sum_list += val
			mp[sum_list] = i
		res = float('inf')
		lvalue = float('inf')
		sum_list = 0
		for (i, val) in enumerate(arr):
			sum_list += val
			if sum_list - target in mp:
				lvalue = min(lvalue, i - mp[sum_list - target])
			if sum_list + target in mp and lvalue != float('inf'):
				res = min(res, lvalue + mp[sum_list + target] - i)
		return -1 if res == float('inf') else res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		if not arr:
			return 0
		min_at_curr = [float('inf')] * len(arr)
		start = end = 0
		currSum = 0
		minSum = float('inf')
		while end < len(arr):
			currSum += arr[end]
			while start <= end and currSum > target:
				currSum -= arr[start]
				start += 1
			if currSum == target:
				minSum = min(minSum, min_at_curr[start - 1] + (end - start) + 1)
				min_at_curr[end] = min(min_at_curr[end - 1], end - start + 1)
			else:
				min_at_curr[end] = min_at_curr[end - 1]
			end += 1
		return minSum if minSum != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		dp = [100001] * n
		presum = {0: -1}
		s = 0
		ans = 100001
		best_so_far = sys.maxsize
		for i in range(n):
			s += arr[i]
			presum[s] = i
			if s - target in presum:
				j = presum[s - target]
				best_so_far = min(best_so_far, i - j)
				if j >= 0:
					ans = min(ans, dp[j] + i - j)
			dp[i] = best_so_far
		return ans if ans < 100001 else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		dp = [float('inf')] * n
		(sums, res) = (0, float('inf'))
		sum_record = {0: -1}
		for (i, num) in enumerate(arr):
			sums += num
			dp[i] = dp[i - 1]
			if sums - target in sum_record:
				cur_len = i - sum_record[sums - target]
				if i - cur_len >= 0:
					res = min(res, cur_len + dp[i - cur_len])
				dp[i] = min(dp[i - 1], cur_len)
			sum_record[sums] = i
		return res if res != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		H = {0: -1}
		total = 0
		M = len(arr) + 1
		for (i, a) in enumerate(arr):
			total += a
			H[total] = i
		result = M
		minL = M
		total = 0
		for (i, a) in enumerate(arr):
			total += a
			if total - target in H:
				minL = min(minL, i - H[total - target])
			if total + target in H and minL < M:
				result = min(result, minL + H[total + target] - i)
		return result if result < M else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		minlen = [float('inf')] * len(arr)
		res = float('inf')
		(l, r, windsum) = (0, 0, 0)
		for r in range(len(arr)):
			windsum += arr[r]
			while windsum > target:
				windsum -= arr[l]
				l += 1
			if windsum == target:
				if minlen[l - 1] != float('inf'):
					temp = minlen[l - 1] + r - l + 1
					res = min(res, temp)
				minlen[r] = min(minlen[r - 1], r - l + 1)
			else:
				minlen[r] = minlen[r - 1]
		return res if res < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		accuArr = []
		y = 0
		for x in arr:
			y += x
			accuArr.append(y)
		bestTill = [float('inf')] * len(arr)
		bestTillNow = float('inf')
		sum2Pos = dict()
		sum2Pos[0] = -1
		res = float('inf')
		for i in range(len(accuArr)):
			currAccu = accuArr[i]
			preSum = currAccu - target
			if preSum in sum2Pos:
				preEnd = sum2Pos[preSum]
				currLength = i - preEnd
				if preEnd != -1:
					res = min(res, currLength + bestTill[preEnd])
				bestTillNow = min(bestTillNow, currLength)
			sum2Pos[currAccu] = i
			bestTill[i] = bestTillNow
		return res if res != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		minLen = float('inf')
		lsize = float('inf')
		preSum = {0: -1}
		curSum = 0
		for (i, val) in enumerate(arr):
			curSum += val
			preSum[curSum] = i
		curSum = 0
		for (i, val) in enumerate(arr):
			curSum += val
			if curSum - target in preSum:
				lsize = min(lsize, i - preSum[curSum - target])
			if curSum + target in preSum and lsize != float('inf'):
				minLen = min(minLen, preSum[curSum + target] - i + lsize)
		return minLen if minLen != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		preSum = {0: -1}
		n = len(arr)
		curSum = 0
		minLen = float('inf')
		lsize = float('inf')
		for i in range(n):
			curSum += arr[i]
			preSum[curSum] = i
		curSum = 0
		for i in range(n):
			curSum += arr[i]
			if curSum - target in preSum:
				lsize = min(lsize, i - preSum[curSum - target])
			if curSum + target in preSum and lsize != float('inf'):
				minLen = min(minLen, preSum[curSum + target] - i + lsize)
		return minLen if minLen != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		(start, ans, sum) = (0, float('inf'), 0)
		best = [float('inf')] * len(arr)
		best_so_far = float('inf')
		for i in range(len(arr)):
			sum += arr[i]
			while sum > target:
				sum -= arr[start]
				start += 1
			if sum == target:
				if start > 0 and best[start - 1] != float('inf'):
					ans = min(ans, best[start - 1] + i - start + 1)
				best_so_far = min(best_so_far, i - start + 1)
			best[i] = best_so_far
		return -1 if ans == float('inf') else ans


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		res = n + 1
		pre = {}
		pre[0] = -1
		dp = [float('inf')] * n
		p = 0
		for (i, a) in enumerate(arr):
			p += a
			dp[i] = dp[i - 1]
			if p - target in pre:
				cur = i - pre[p - target]
				if pre[p - target] >= 0 and dp[pre[p - target]] != float('inf'):
					res = min(res, cur + dp[pre[p - target]])
				dp[i] = min(i - pre[p - target], dp[i - 1])
			pre[p] = i
		return -1 if res == n + 1 else res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		l = 0
		currentSum = 0
		res = -1
		record = [-1] * len(arr)
		for r in range(len(arr)):
			currentSum += arr[r]
			while currentSum > target and l < r:
				currentSum -= arr[l]
				l += 1
			if currentSum == target:
				curr = r - l + 1
				print(curr)
				if record[l - 1] != -1:
					res = curr + record[l - 1] if res == -1 else min(res, curr + record[l - 1])
				record[r] = curr if record[r - 1] == -1 else min(record[r - 1], curr)
			else:
				record[r] = record[r - 1]
		return res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix_sum2_idx = defaultdict(int)
		prefix_sum2_idx[0] = -1
		prefix_sum = 0
		n = len(arr)
		for i in range(n):
			prefix_sum += arr[i]
			prefix_sum2_idx[prefix_sum] = i
		prefix_sum = 0
		l_min_len = float('inf')
		min_len = float('inf')
		for i in range(n):
			prefix_sum += arr[i]
			if prefix_sum - target in prefix_sum2_idx:
				l_min_len = min(l_min_len, i - prefix_sum2_idx[prefix_sum - target])
			if prefix_sum + target in prefix_sum2_idx:
				min_len = min(min_len, prefix_sum2_idx[prefix_sum + target] - i + l_min_len)
		return -1 if min_len == float('inf') else min_len


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		for i in range(1, len(arr)):
			arr[i] += arr[i - 1]
		index = {0: -1}
		best_till = [float('inf')] * len(arr)
		res = float('inf')
		best = float('inf')
		for (i, val) in enumerate(arr):
			if val - target in index:
				start_of_window = index[val - target]
				length = i - start_of_window
				res = min(res, best_till[start_of_window + 1] + length)
				best = min(best, length)
			if i + 1 < len(best_till):
				best_till[i + 1] = best
			index[val] = i
		return -1 if res == float('inf') else res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		sums_list = [0]
		sums_dict = {0: 0}
		s = 0
		for i in range(len(arr)):
			s += arr[i]
			sums_dict[s] = i + 1
			sums_list.append(s)
		lengths = [0] * len(sums_list)
		min_length = float('+inf')
		for start in range(len(sums_list) - 1, -1, -1):
			val = sums_list[start] + target
			if val in sums_dict:
				end = sums_dict[val]
				min_length = min(min_length, end - start)
			lengths[start] = min_length
		min_length = float('+inf')
		for start in range(len(sums_list)):
			val = sums_list[start] + target
			if val in sums_dict:
				end = sums_dict[val]
				l = end - start + lengths[end]
				min_length = min(min_length, l)
		if min_length != float('+inf'):
			return min_length
		else:
			return -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		mapsum = {}
		mapsum[0] = -1
		totsum = 0
		best_till = [math.inf] * len(arr)
		best = math.inf
		end = -1
		res = float('inf')
		for i in range(len(arr)):
			totsum += arr[i]
			if totsum - target in mapsum:
				end = mapsum[totsum - target]
				if end > -1:
					res = min(res, i - end + best_till[end])
				best = min(best, i - end)
			best_till[i] = best
			mapsum[totsum] = i
		if res < math.inf:
			return res
		return res if res < math.inf else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		dp = [float('inf') for _ in range(n + 1)]
		ans = float('inf')
		start = 0
		curr_sum = 0
		for end in range(n):
			curr_sum += arr[end]
			while start < end and curr_sum > target:
				curr_sum -= arr[start]
				start += 1
			if curr_sum == target:
				ans = min(ans, end - start + 1 + dp[start - 1])
				dp[end] = min(dp[end - 1], end - start + 1)
			else:
				dp[end] = dp[end - 1]
		return ans if ans != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix = []
		for n in arr:
			if len(prefix) == 0:
				prefix.append(n)
			else:
				prefix.append(prefix[-1] + n)
		indexMap = {}
		indexMap[0] = -1
		best = output = float('inf')
		best_till = [float('inf')] * len(arr)
		for (i, p) in enumerate(prefix):
			if p - target in indexMap:
				output = min(output, i - indexMap[p - target] + best_till[indexMap[p - target]])
				best = min(best, i - indexMap[p - target])
			best_till[i] = best
			indexMap[p] = i
		return -1 if output == float('inf') else output


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		dp = [float('inf') for i in range(len(arr))]
		curr_sum = 0
		hist = {0: -1}
		res = float('inf')
		shortest_length = float('inf')
		for (i, num) in enumerate(arr):
			curr_sum += num
			diff = curr_sum - target
			if diff in hist:
				index = hist[diff]
				length = i - index
				if index > 0 and dp[index] != float('inf'):
					res = min(res, dp[index] + length)
				shortest_length = min(shortest_length, length)
			hist[curr_sum] = i
			dp[i] = shortest_length
		return res if res != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		p = [0]
		m = {0: -1}
		minLen = [float('inf')]
		cur = 0
		ans = best = float('inf')
		for (i, a) in enumerate(arr):
			cur += a
			p.append(cur)
			if cur - target in m:
				ans = min(ans, i - m[cur - target] + minLen[m[cur - target] + 1])
				best = min(i - m[cur - target], best)
			minLen.append(best)
			m[cur] = i
		return ans if ans != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		(start, window_sum, result) = (0, 0, float('inf'))
		pre_min = len(arr) * [float('inf')]
		for (i, num) in enumerate(arr):
			window_sum += num
			while window_sum > target:
				window_sum -= arr[start]
				start += 1
			if window_sum == target:
				curr_len = i - start + 1
				result = min(result, curr_len + pre_min[start - 1])
				pre_min[i] = min(curr_len, pre_min[i - 1])
			else:
				pre_min[i] = pre_min[i - 1]
		return result if result < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		(prefxSum, prefx) = (0, [])
		(suffxSum, suffx) = (sum(arr), [])
		dct = {0: -1}
		dp = [float('inf')] * len(arr)
		for i in range(0, len(arr)):
			x = arr[i]
			prefxSum += x
			prefx.append(prefxSum)
			suffx.append(suffxSum)
			suffxSum -= x
			dct[prefxSum] = i
		prefxSum = 0
		mn = float('inf')
		for i in range(0, len(arr)):
			prefxSum += arr[i]
			if prefxSum - target in dct:
				start = dct[prefxSum - target]
				if start > -1:
					if dp[start] != float('inf'):
						mn = min(mn, dp[start] + i - start)
					dp[i] = min(dp[i - 1], i - start)
				else:
					dp[i] = i + 1
			elif i > 0:
				dp[i] = dp[i - 1]
		return mn if mn != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		if not arr:
			return 0
		n = len(arr)
		dp = [float('inf')] * n
		presum = 0
		indexes = {0: -1}
		res = float('inf')
		for (i, a) in enumerate(arr):
			presum += a
			if i > 0:
				dp[i] = dp[i - 1]
			if presum - target in indexes:
				idx = indexes[presum - target]
				l = i - idx
				if dp[idx] != float('inf'):
					res = min(res, l + dp[idx])
				dp[i] = min(dp[i], l)
			indexes[presum] = i
		return res if res < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix_sum = [float('inf')] * len(arr)
		suffix_sum = [float('inf')] * len(arr)
		prefix_map = {0: -1}
		suffix_map = {0: len(arr)}
		cur_sum = 0
		_min_till_now = float('inf')
		for i in range(len(arr) - 1):
			cur_sum += arr[i]
			if cur_sum - target in prefix_map:
				_min_till_now = min(_min_till_now, i - prefix_map[cur_sum - target])
			prefix_sum[i + 1] = _min_till_now
			prefix_map[cur_sum] = i
		cur_sum = 0
		_min_till_now = float('inf')
		for i in range(len(arr) - 1, -1, -1):
			cur_sum += arr[i]
			if cur_sum - target in suffix_map:
				_min_till_now = min(_min_till_now, suffix_map[cur_sum - target] - i)
			suffix_sum[i] = _min_till_now
			suffix_map[cur_sum] = i
		ans = min([x + y for (x, y) in zip(prefix_sum, suffix_sum)])
		return ans if ans != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		if not arr:
			return -1
		prefixes = [0] * len(arr)
		suffixes = [0] * len(arr)
		left = right = 0
		curr = 0
		min_len = float('inf')
		while right < len(arr):
			curr += arr[right]
			while curr >= target and left <= right:
				if curr == target:
					l = right - left + 1
					if l < min_len:
						min_len = l
				curr -= arr[left]
				left += 1
			prefixes[right] = min_len
			right += 1
		left = right = len(arr) - 1
		curr = 0
		min_len = float('inf')
		while left >= 0:
			curr += arr[left]
			while curr >= target and left <= right:
				if curr == target:
					l = right - left + 1
					if l < min_len:
						min_len = l
				curr -= arr[right]
				right -= 1
			suffixes[left] = min_len
			left -= 1
		min_len = float('inf')
		for i in range(len(arr) - 1):
			s = prefixes[i] + suffixes[i + 1]
			if s < min_len:
				min_len = s
		return min_len if min_len != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		arr_len = len(arr)
		dp = [sys.maxsize] * arr_len
		left = right = 0
		sum_tmp = 0
		(length, ans_len) = (sys.maxsize, sys.maxsize)
		while right < arr_len:
			sum_tmp += arr[right]
			while sum_tmp > target:
				sum_tmp -= arr[left]
				left += 1
			if sum_tmp == target:
				if left > 0 and dp[left - 1] != sys.maxsize:
					length = min(length, dp[left - 1] + right - left + 1)
				ans_len = min(ans_len, right - left + 1)
			dp[right] = ans_len
			right += 1
		return length if length != sys.maxsize else -1


from collections import *

class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		mapper = defaultdict(int)
		prefix = [0] * len(arr)
		prefix[0] = arr[0]
		mapper[0] = -1
		mapper[arr[0]] = 0
		for i in range(1, len(arr)):
			prefix[i] = prefix[i - 1] + arr[i]
			mapper[prefix[i]] = i
		cumu = count = 0
		l = r = None
		ans = float('inf')
		vis = []
		for (i, a) in enumerate(arr):
			cumu += a
			if cumu - target in mapper:
				if l == None:
					count += 1
					l = i - mapper[cumu - target]
					vis.append((mapper[cumu - target] + 1, i))
				else:
					l = min(l, i - mapper[cumu - target])
			if l != None and cumu + target in mapper:
				ans = min(ans, mapper[cumu + target] - i + l)
		if ans == float('inf'):
			return -1
		return ans


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		curr_sum = 0
		curr_best = -1
		lo = hi = 0
		lmin = []
		while lo <= hi < n:
			curr_sum += arr[hi]
			while curr_sum > target and lo <= hi:
				curr_sum -= arr[lo]
				lo += 1
			if curr_sum == target:
				tmp = hi - lo + 1
				if tmp < curr_best or curr_best == -1:
					curr_best = tmp
			lmin.append(curr_best)
			hi += 1
		curr_sum = 0
		curr_best = -1
		lo = hi = n - 1
		rmin = [-1]
		while 0 < lo <= hi:
			curr_sum += arr[lo]
			while curr_sum > target and lo <= hi:
				curr_sum -= arr[hi]
				hi -= 1
			if curr_sum == target:
				tmp = hi - lo + 1
				if tmp < curr_best or curr_best == -1:
					curr_best = tmp
			rmin.append(curr_best)
			lo -= 1
		rmin = rmin[::-1]
		res = -1
		for i in range(n):
			if lmin[i] != -1 and rmin[i] != -1:
				if res == -1 or lmin[i] + rmin[i] < res:
					res = lmin[i] + rmin[i]
		return res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		min_lens = [sys.maxsize] * n
		l = 0
		min_len = sys.maxsize
		prefix = 0
		ans = sys.maxsize
		for r in range(n):
			prefix += arr[r]
			while prefix > target:
				prefix -= arr[l]
				l += 1
			if prefix == target:
				cur_len = r - l + 1
				if l > 0 and min_lens[l - 1] != sys.maxsize:
					ans = min(ans, cur_len + min_lens[l - 1])
				min_len = min(min_len, cur_len)
			min_lens[r] = min_len
		return -1 if ans == sys.maxsize else ans


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		LARGE_NUMBER = 1000000000
		if not arr:
			return -1
		psum = [0] * (len(arr) + 1)
		sum2i = {}
		for i in range(len(arr)):
			psum[i + 1] = psum[i] + arr[i]
		res = LARGE_NUMBER
		dp = [LARGE_NUMBER] * (len(arr) + 1)
		for (i, x) in enumerate(psum):
			assert x not in sum2i
			sum2i[x] = i
			if i > 0:
				dp[i] = dp[i - 1]
			if psum[i] - target in sum2i:
				j = sum2i[psum[i] - target]
				dp[i] = min(dp[i], i - j)
				if dp[j] != LARGE_NUMBER:
					res = min(res, dp[j] + i - j)
		return res if res != LARGE_NUMBER else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		presum = [0] * len(arr)
		c = 0
		for i in range(len(arr)):
			c += arr[i]
			presum[i] = c
		dic = {0: -1}
		index = [0] * len(arr)
		short = [0] * len(arr)
		temp = sys.maxsize
		for i in range(len(arr)):
			if presum[i] - target in dic:
				index[i] = i - dic[presum[i] - target]
				temp = min(temp, i - dic[presum[i] - target])
			dic[presum[i]] = i
			short[i] = temp
		ans = sys.maxsize
		print((index, short))
		for i in range(1, len(arr)):
			if index[i] > 0 and i - index[i] >= 0 and (short[i - index[i]] != sys.maxsize):
				ans = min(ans, short[i - index[i]] + index[i])
		if ans == sys.maxsize:
			return -1
		return ans


from collections import deque
from itertools import accumulate

class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		(x, n) = (list(accumulate(arr, initial=0)), len(arr))
		(s, d) = ([], {})
		for i in range(n + 1):
			y = x[i] - target
			if y in d:
				s.append([i - d[y], d[y], i])
			d[x[i]] = i
		for k in range(len(s) - 2, -1, -1):
			s[k][0] = min(s[k][0], s[k + 1][0])
		(ans, queue) = (float('inf'), deque([]))
		for (d, i, j) in s:
			while queue and queue[0][-1] <= i:
				ans = min(ans, queue.popleft()[0] + d)
			queue.append((j - i, i, j))
		return ans if ans < float('inf') else -1


from collections import defaultdict

class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix = defaultdict(list)
		best_till = [sys.maxsize] * len(arr)
		res = sys.maxsize
		prefix[0].append(-1)
		temp_s = 0
		for (i, ele) in enumerate(arr):
			temp_s += ele
			prefix[temp_s].append(i)
			if temp_s - target in prefix:
				for index in prefix[temp_s - target]:
					best_till[i] = min(best_till[i - 1], i - index)
					if index != -1:
						res = min(res, best_till[index] + i - index)
			elif i >= 1:
				best_till[i] = best_till[i - 1]
		return -1 if res == sys.maxsize else res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		(ptr1, ptr2) = (0, 0)
		s = arr[0]
		m = [-1] * len(arr)
		ans = -1
		global_min = -1
		while ptr2 < len(arr):
			if global_min > 0:
				m[ptr2] = global_min
			if s == target:
				m[ptr2] = min(global_min, ptr2 - ptr1 + 1) if global_min > 0 else ptr2 - ptr1 + 1
				global_min = m[ptr2]
				if ptr1 - 1 >= 0 and m[ptr1 - 1] > 0:
					ans = min(ans, m[ptr1 - 1] + ptr2 - ptr1 + 1) if ans > 0 else m[ptr1 - 1] + ptr2 - ptr1 + 1
				ptr1 += 1
				ptr2 += 1
				if ptr2 < len(arr):
					s = s - arr[ptr1 - 1] + arr[ptr2]
			elif s > target:
				ptr1 += 1
				s = s - arr[ptr1 - 1]
				if ptr1 > ptr2 and ptr2 + 1 < len(arr):
					ptr2 += 1
					s = s + arr[ptr2]
			else:
				ptr2 += 1
				if ptr2 < len(arr):
					s = s + arr[ptr2]
		return ans


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		nums = [0 for i in range(len(arr))]
		nums[0] = arr[0]
		for i in range(1, len(arr)):
			nums[i] = nums[i - 1] + arr[i]
		best = [float('inf') for i in range(len(arr))]
		ans = float('inf')
		size = float('inf')
		l = 0
		r = 0
		window = 0
		while l <= r and r < len(arr):
			window += arr[r]
			while l <= r and window > target:
				window -= arr[l]
				l += 1
			if window == target:
				ans = min(ans, r - l + 1 + best[l - 1])
				best[r] = min(best[r - 1], r - l + 1)
			else:
				best[r] = best[r - 1]
			r += 1
		if ans == float('inf'):
			return -1
		else:
			return ans


import bisect

class Solution:

	def minSumOfLengths(self, arr, target):
		lo = 0
		hi = 0
		cur = arr[0]
		running_min = []
		ans = 1000000000.0
		while lo <= hi and hi < len(arr):
			if cur >= target:
				if cur == target:
					best_range = hi - lo + 1
					if len(running_min):
						best_range = min(best_range, running_min[-1][1])
						prev_index = bisect.bisect(running_min, (lo, -1)) - 1
						if 0 <= prev_index < len(running_min):
							ans = min(ans, hi - lo + 1 + running_min[prev_index][1])
					running_min.append((hi, best_range))
				cur -= arr[lo]
				lo += 1
				if hi < lo:
					hi = lo
				else:
					continue
			else:
				hi += 1
			if hi < len(arr):
				cur += arr[hi]
		return ans if ans != 1000000000.0 else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		best_so_far = [float('inf') for i in range(len(arr) + 1)]
		prefix_sum = 0
		prefix_sum_to_idx = {0: -1}
		res = float('inf')
		for (i, v) in enumerate(arr):
			prefix_sum += v
			best_so_far[i + 1] = best_so_far[i]
			prev_sum = prefix_sum - target
			if prev_sum in prefix_sum_to_idx:
				res = min(res, best_so_far[prefix_sum_to_idx[prev_sum] + 1] + i - prefix_sum_to_idx[prev_sum])
				best_so_far[i + 1] = min(best_so_far[i], i - prefix_sum_to_idx[prev_sum])
			prefix_sum_to_idx[prefix_sum] = i
		return -1 if res == float('inf') else res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		best_to = [n + 1 for _ in range(n)]
		best_from = dict()
		min_total = n + 1
		min_left = n + 1
		sum_left = 0
		s_left = 0
		e_left = 0
		for i in range(n):
			sum_left += arr[i]
			if sum_left == target:
				best_to[i] = i - s_left + 1
				best_from[s_left] = i - s_left + 1
			elif sum_left > target:
				while s_left < i and sum_left > target:
					sum_left -= arr[s_left]
					s_left += 1
				if sum_left == target:
					best_to[i] = i - s_left + 1
					best_from[s_left] = i - s_left + 1
		for i in range(1, n):
			best_to[i] = min(best_to[i], best_to[i - 1])
		for i in range(n - 1):
			if best_to[i] > n:
				continue
			if i + 1 in best_from:
				min_total = min(min_total, best_to[i] + best_from[i + 1])
		if min_total > n:
			return -1
		return min_total


from collections import defaultdict as ddic

class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		dic = ddic(int)
		sum_ = 0
		dic[0] = -1
		L = len(arr)
		dp = [0] * L
		dp2 = [-1] * L
		res = float('inf')
		for i in range(L):
			sum_ += arr[i]
			dic[sum_] = i
			if sum_ - target in dic:
				dp[i] = i - dic[sum_ - target]
				dp2[i] = i - dic[sum_ - target]
				if i != 0:
					if dp2[i - 1] != -1:
						dp2[i] = min(dp2[i], dp2[i - 1])
				if dp2[dic[sum_ - target]] != -1:
					res = min(res, dp[i] + dp2[dic[sum_ - target]])
			if dp2[i] == -1:
				if i != 0:
					dp2[i] = dp2[i - 1]
		if res > L:
			return -1
		return res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		minlens = [float('inf')] * n
		res = float('inf')
		sum1 = 0
		s = 0
		min_len = float('inf')
		for e in range(n):
			sum1 += arr[e]
			while sum1 > target:
				sum1 -= arr[s]
				s += 1
			if sum1 == target:
				cur_len = e - s + 1
				if s > 0 and minlens[s - 1] != float('inf'):
					res = min(res, cur_len + minlens[s - 1])
				min_len = min(min_len, cur_len)
			minlens[e] = min_len
		if res != float('inf'):
			return res
		return -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		len_to_start = collections.defaultdict(list)
		(start, end) = (0, 1)
		tmp_sum = arr[0]
		(earliest_end, latest_start) = (len(arr), 0)
		while start < len(arr):
			while end < len(arr) and tmp_sum < target:
				tmp_sum += arr[end]
				end += 1
			if tmp_sum == target:
				len_to_start[end - start].append(start)
				earliest_end = min(earliest_end, end)
				latest_start = max(latest_start, start)
			tmp_sum -= arr[start]
			start += 1
		if earliest_end > latest_start:
			return -1
		for (l, starts) in list(len_to_start.items()):
			if len(starts) > 2:
				len_to_start[l] = [starts[0], starts[-1]]
		shortest = len(arr)
		for l1 in len_to_start:
			for s1 in len_to_start[l1]:
				for l2 in len_to_start:
					for s2 in len_to_start[l2]:
						if l1 + l2 >= shortest:
							continue
						if s1 < s2 and s1 + l1 <= s2:
							shortest = l1 + l2
						if s2 < s1 and s2 + l2 <= s1:
							shortest = l1 + l2
		return shortest


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		(left, right) = (0, 0)
		valid_subarray_lengths = [0 for _ in range(len(arr))]
		cum_sum = 0
		for i in range(len(arr)):
			cum_sum += arr[i]
			right = i
			while cum_sum > target:
				cum_sum -= arr[left]
				left += 1
			if cum_sum == target:
				valid_subarray_lengths[i] = right - left + 1
		prefix_min_lengths = [None for _ in range(len(valid_subarray_lengths))]
		prefix_min = float('inf')
		for i in range(len(valid_subarray_lengths)):
			prefix_min = min(prefix_min, valid_subarray_lengths[i] if valid_subarray_lengths[i] else float('inf'))
			prefix_min_lengths[i] = prefix_min
		res = float('inf')
		for i in range(len(valid_subarray_lengths)):
			if valid_subarray_lengths[i] != 0 and i - valid_subarray_lengths[i] >= 0 and (prefix_min_lengths[i - valid_subarray_lengths[i]] > 0):
				res = min(res, valid_subarray_lengths[i] + prefix_min_lengths[i - valid_subarray_lengths[i]])
		return res if res != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		lens_s = [math.inf] * len(arr)
		lens_e = [math.inf] * len(arr)
		cs = s = e = 0
		for i in range(len(arr)):
			cs += arr[e]
			while cs >= target:
				if cs == target:
					lens_e[e] = lens_s[s] = e + 1 - s
				cs -= arr[s]
				s += 1
			e += 1
		forward = [math.inf] * (len(arr) + 1)
		for i in range(1, len(arr)):
			forward[i] = min(lens_e[i - 1], forward[i - 1])
		backward = [math.inf] * (len(arr) + 1)
		for i in reversed(list(range(0, len(arr)))):
			backward[i] = min(lens_s[i], backward[i + 1])
		best = math.inf
		for (f, b) in zip(forward, backward):
			best = min(best, f + b)
		if best == math.inf:
			return -1
		return best


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		prefix = {0: -1}
		(res, best, dp) = (sys.maxsize, sys.maxsize, [sys.maxsize] * len(arr))
		for (i, acc) in enumerate(itertools.accumulate(arr)):
			if acc - target in prefix:
				end = prefix[acc - target]
				if end > -1:
					res = min(res, i - end + dp[end])
				best = min(best, i - end)
			dp[i] = best
			prefix[acc] = i
		return -1 if res == sys.maxsize else res


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		l = len(arr)
		(left, right, pre) = ([l] * l, [l] * l, {0: -1})
		p = 0
		for i in range(l):
			p += arr[i]
			if p - target in pre:
				prev = pre[p - target]
				left[i] = i - prev
				if prev >= 0:
					right[prev] = min(right[prev], i - prev)
			pre[p] = i
		for i in range(1, l):
			left[i] = min(left[i], left[i - 1])
		for i in range(l - 2, -1, -1):
			right[i] = min(right[i], right[i + 1])
		ans = l + 1
		ans = min((left[i] + right[i] if left[i] < l and right[i] < l else l + 1 for i in range(l)))
		return ans if ans < l + 1 else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		left = [float('inf')] * n
		memo = {0: -1}
		current = 0
		for k in range(n):
			if k > 0:
				left[k] = left[k - 1]
			current += arr[k]
			if current - target in memo:
				left[k] = min(left[k], k - memo[current - target])
			memo[current] = k
		right = [float('inf')] * n
		memo = {0: n}
		current = 0
		for k in range(n - 1, -1, -1):
			if k < n - 1:
				right[k] = right[k + 1]
			current += arr[k]
			if current - target in memo:
				right[k] = min(right[k], memo[current - target] - k)
			memo[current] = k
		ans = float('inf')
		for k in range(n - 1):
			ans = min(ans, left[k] + right[k + 1])
		return ans if ans != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:

		def getPrefix(arr):
			m = {0: -1}
			prefix = [float('inf')]
			s = 0
			for (i, n) in enumerate(arr):
				s += n
				minn = prefix[-1]
				if s - target in m:
					minn = min(i - m[s - target], minn)
				prefix.append(minn)
				m[s] = i
			prefix.pop(0)
			return prefix
		prefix = getPrefix(arr)
		sufix = list(reversed(getPrefix(reversed(arr))))
		ans = float('inf')
		for i in range(len(arr) - 1):
			ans = min(ans, prefix[i] + sufix[i + 1])
		return ans if ans != float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		d = {}
		d[0] = -1
		possible_sum = {0}
		cur_sum = 0
		for (i, a) in enumerate(arr):
			cur_sum += a
			possible_sum.add(cur_sum)
			d[cur_sum] = i
		till_len = [float('inf')] * len(arr)
		for s in possible_sum:
			if s + target in possible_sum:
				till_len[d[s + target]] = d[s + target] - d[s]
		ans = float('inf')
		pre_min = [float('inf')] * len(arr)
		for (i, t) in enumerate(till_len):
			if i == t - 1:
				pre_min[i] = t
			else:
				pre_min[i] = min(t, pre_min[i - 1])
				if t < float('inf') and pre_min[i - t] < float('inf'):
					ans = min(ans, t + pre_min[i - t])
		return ans if ans < float('inf') else -1


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		n = len(arr)
		prefixSum = [0] * n
		targetSum = [sys.maxsize] * n
		beforeSum = [sys.maxsize] * n
		afterSum = [sys.maxsize] * n
		sumDict = {0: -1}
		total = 0
		for i in range(n):
			total += arr[i]
			prefixSum[i] = total
			if total - target in sumDict:
				index = sumDict[total - target]
				targetSum[i] = i - index
			sumDict[total] = i
		minValue = sys.maxsize
		for i in range(n):
			minValue = min(targetSum[i], minValue)
			beforeSum[i] = minValue
		minValue = sys.maxsize
		for i in reversed(list(range(1, n))):
			startIndex = i - targetSum[i]
			if startIndex >= 0:
				afterSum[startIndex] = min(afterSum[startIndex], targetSum[i])
		minValue = sys.maxsize
		for i in range(len(arr)):
			minValue = min(minValue, beforeSum[i] + afterSum[i])
		if minValue == sys.maxsize:
			minValue = -1
		return minValue


class Solution:

	def minSumOfLengths(self, arr: List[int], target: int) -> int:
		curr_sum = 0
		intervals = [(-200002, -100001), (-200002, -100001)]
		h = {0: -1}
		f = [[100001] * len(arr) for i in range(2)]
		for (index, a) in enumerate(arr):
			curr_sum += a
			f[1][index] = min(f[0][h[curr_sum - target]] + index - h[curr_sum - target] if curr_sum - target in h else 100001, f[1][index - 1])
			f[0][index] = min(f[0][index - 1] if index >= 1 else 100001, index - h[curr_sum - target] if curr_sum - target in h else 100001)
			h[curr_sum] = index
		return -1 if f[-1][-1] >= 100001 else f[-1][-1]