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

Difficulty: interview

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:
#         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:
        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:
        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[i] is the min len of subarray with sum in arr[:i]
        # suffix[i] is the min len of subarray with sum in arr[i:]
        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:
        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)
        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:
  # 864 ms
  def minSumOfLengths(self, arr, target):
    result = inf = 2**31-1
    i = window = count = 0
    # preMin: store previous shortest length
    preMin = [(-1, inf)]

    # i: window start, j: window end
    for j, num in enumerate(arr):
     # print(preMin)
      window += num
      while window > target:
        window -= arr[i]
        i += 1
      if window == target:
        # curr: current length
        curr = j - i + 1
        n = 0 
        # find first minimal length n before window start i
        for index, length in preMin[::-1]:
          if index <= i-1: 
            n = length           
            break
        # update result 
        if result > curr + n: result = curr + n
            
        # update shortest length
        if curr < preMin[-1][-1]: preMin.append((j, curr))
          
        # early stopping if found two single targets
      #  if curr == 1: count += 1
      #  if count == 2: return 2

    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):
            # print(c, target, target-c, h2idx)
            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])
            
# t = 7
# [ 2, 2, 3, 4, 3, 4]

    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
            
        #print(sumArr)
        #print(sumMap)
        
        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):
            #print(\"arr:%d\"%(sumArr[i]))
            #print(sumMap.get(sumArr[i] - target))
            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 # Naturally impossible length. Will be updated if any possible case exist. Will tell when no possible case
        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:
        #    h[key] stores list of indices, let ind = h[key][-1] 
        #    Here, run[ind] == key (INCLUDING arr[ind - 1]) 
        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

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] = min(minSub[i - 1], i - 0 + 1) 
            elif currentSum - target in dic:
                minSub[i] =  min(minSub[i - 1], i - dic[currentSum - target]) 
            else:
                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

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] + 1
            minSub[i] = min(minSub[i - 1], minSub[i] )
            dic[currentSum] = i + 1
        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:
        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:
        INF = len(arr) + 1
        best_at_i = [INF]*len(arr) # the ith index represents the smallest length subarray we've found ending <= i that sums to target
        best = INF # output 
        curr_sum = 0 # current sum between left and right
        
        left = 0
        for right in range(len(arr)):
            # update the running sum
            curr_sum += arr[right]
            
            # arr is strictly positive, so shrink window until we're not above target
            while curr_sum > target and left <= right:
                curr_sum -= arr[left]
                left += 1
                
            if curr_sum == target:
                # we have a new shortest candidate to consider
                best = min(best, best_at_i[left-1] + right - left + 1)
                best_at_i[right] = min(best_at_i[right-1], right - left + 1)
            else:
                # best we've seen is the previous best (overlaps to end if right == 0)
                best_at_i[right] = best_at_i[right-1]

        if best == INF:
            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:
                #   找到一个target
                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:
                #   找到一个target
                t = sufsum[xx] - i
            suffix[i] = min(suffix[i+1], t)
                
        # print(prefix)
        # print(suffix)
        
        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 )                     # from front
        dp_right = get_sub_arrays( arr[::-1] )[::-1]        # from backwards
        
        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:
  # 864 ms
  def minSumOfLengths(self, arr, target):
    result = inf = 2**31-1
    i = window = count = 0
    # preMin: store previous shortest length
    preMin = deque([(-1, inf)])

    # i: window start, j: window end
    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: current length
        curr = j - i + 1

        # find first minimal length n before window start i
        n = preMin[0][1]
        # update result if less    
        if result > curr + n: result = curr + n
            
        # update shortest length if less
        if curr < preMin[-1][-1]: preMin.append((j, curr))
          
        # early stopping if found two single targets
        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)

    # i: window start, j: window end
    for j in range(len(arr)):
      window += arr[j]
      while window > target:
        window -= arr[i]
        i += 1
      if window == target:
        # curr: length
        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:
        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
        
        def get_min_right():
            min_right = [float('inf') for _ in range(n)]
            window = 0
            r = n - 1
            for l in range(n - 1, -1, -1):
                window += arr[l]
                while window > target:
                    window -= arr[r]
                    r -= 1
                if window == target:
                    min_right[l] = r - l + 1
                if l < n - 1:
                    min_right[l] = min(min_right[l], min_right[l - 1])
            return min_right
        
        min_left = get_min(arr)
        min_right = get_min_right() # get_min(arr[::-1])[::-1]
        print((min_right[::-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: List[int], target: int) -> int:
        result = float('inf')
        # prefix shortest length read from left to right
        leftmin = self.getMinLen(arr, target, True)
        # suffix shortest length read from right to left
        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 it's reading from right to left, then reverse input array
        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] > target
                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] > target
                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])  
            
#         print(prefix)
#         print(suffix)
        
        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:
        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 # Naturally impossible length. Will be updated if any possible case exist. Will tell when no possible case
        min_left = n + 1
        sum_left = 0
        s_left = 0
        
        for i in range(n):
            sum_left = acc[i] - acc[s_left-1]
            # if i == 3:
                # print(s_left)
                # print(sum_left)
            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:
                    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])
            
        # print(best_to)
        # print(best_from)
        
        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:
        dp = [len(arr) + 1] * len(arr)  # min valid subarray length for arr[:i + 1]
        table = {0: -1}  # key: prefix sum, value: latest index
        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
        #print(queue,min_q)
        while(pointer2<len(queue)):
            if queue[pointer2][0]<=queue[pointer1][1]:
                pointer2+=1
                continue
            #print(pointer1,pointer2,res)
            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) #minimum interval length so far from left
        msr = [math.inf] * len(arr) # minimum interval length so far fromm right
        
        
        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:
  # 864 ms
  def minSumOfLengths(self, arr, target):
    result = inf = 2**31-1
    i = window = count = 0
    # preMin: store previous shortest length
    preMin = [(-1, inf)]

    # i: window start, j: window end
    for j, num in enumerate(arr):
      window += num
      while window > target:
        window -= arr[i]
        i += 1
      if window == target:
        # curr: current length
        curr = j - i + 1
        n = 0 
        # find first minimal length before window start i
        for index, length in preMin[::-1]:
          if index <= i-1: 
            n = length           
            break
        # update result if less    
        if result > curr + n:
            result = curr + n
        # update shortest length if less
        if curr < preMin[-1][-1]:
          preMin.append((j, curr))
        # early stopping if found two single targets
      #  if curr == 1: count += 1
      #  if count == 2: return 2

    return result if result < inf else -1

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)] # best subarray length until reach index i (exclusive)
        presum = 0
        maps = {} # key: sum, val: index
        maps[0] = -1
        ans = best = MAX
        for i, v in enumerate(arr):
            presum += v
            # check if we have a subarray
            key = presum - target
            if key in maps:
                left_idx = maps[key]  # sums(arr[left_idx+1:i+1])
                curr_len = i - left_idx
                best = min(best, curr_len) 
                
                # check if this could be a second subarray
                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
    


class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        # dp_leftは、右から見たときの最小長さarrayを保存
        # dp_rightは、左から見たときの最小長さarrayを保存
        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 )                     # from front
        dp_right = get_sub_arrays( arr[::-1] )[::-1]        # from backwards
        
        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


INF = int(1e9)

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

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

class Solution:
  def minSumOfLengths(self, arr, target):
    result = inf = 2**31-1
    i = window = count = 0
    # preMin: store previous shortest length
    preMin = [(-1, inf)]

    # i: window start, j: window end
    for j, num in enumerate(arr):
      window += num
      while window > target:
        window -= arr[i]
        i += 1
      if window == target:
        # curr: current length
        curr = j - i + 1
        n = 0 
        # find first minimal length before window start i
        for index, length in preMin[::-1]:
          if index <= i-1: 
            n = length           
            break
        # update result if less    
        if result > curr + n:
            result = curr + n
        # update shortest length if less
        if curr < preMin[-1][-1]:
          preMin.append((j, curr))
        # early stopping if found two single targets
        if curr == 1: count += 1
        if count == 2: return 2

    return result if result < inf else -1

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:
        # What's the best I can do ENDING at this index.
        self.preceeding_soln_lens = [sys.maxsize] * len(arr)
        min_len_sum = sys.maxsize
        buffer = []
        buffer_sum = 0
        buffer_len = 0

        i = 0
        # O(N)
        while i < len(arr):
            # update state
            buffer_sum += arr[i]
            buffer_len += 1
            buffer.append(i)

            sub_array_end_idx = buffer[-1]

            # check constraint
            if buffer_sum < target:
                # copy over the previous one
                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:
                    # check for the min
                    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:
        # What's the best I can do ENDING at this index.
        self.preceeding_soln_lens = [sys.maxsize] * len(arr)
        min_len_sum = sys.maxsize
        buffer = []
        buffer_sum = 0
        buffer_len = 0

        i = 0
        # O(N)
        while i < len(arr):
            # update state
            buffer_sum += arr[i]
            buffer_len += 1
            buffer.append(i)

            sub_array_end_idx = buffer[-1]

            # check constraint
            if buffer_sum < target:
                # copy over the previous one
                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:
                    # check for the min
                    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

# Reference : https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/discuss/685486/JAVA-O(N)-Time-Two-Pass-Solution-using-HashMap.


class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        
        # prefix sum
        # in dictionary, store {sum_until_idx: idx}
        
        # iterate through the array and keep current sum
        # 1. have a left_min_len to track the min length until current idx
        # if current sum + target is in the dictionary, 
        # then it means there is a target in the right side of the array
        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)
        
        # print(left)
        # print(right)
        
        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)
        
        # print(left_sub_array, right_sub_array)
        
        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 = {}  #include start-range
        posleft = 0
        posright = 0
        currSum = 0
        while  posright < len(arr):
            currSum += arr[posright]
            if currSum  == target:
                #update rifht of i, including i
                rightList = rightSizes.get(posleft,[])
                rightList.append(posright-posleft + 1)
                rightSizes[posleft] = rightList
                #update left of i, not including i
                if (posright +1 < len(arr)):
                    leftList = leftSizes.get(posright+1,[])
                    leftList.append(posright-posleft + 1)
                    leftSizes[posright+1]=leftList
                #move pointers to the right
                posright +=1
                currSum -= arr[posleft]
                posleft +=1
            elif currSum  > target:
                #remove leftmost element 
                currSum =  currSum - arr[posright] - arr[posleft] 
                posleft +=1
            else: #currSum < target
                #include current element move right pointer
                posright +=1
        #print ('left', leftSizes)   
        #print('right', rightSizes)
        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):
        # 3 4 5
        # 1 3 2.    target = 6
        # update i  =3  for right or equal of 3
        # update i = 6 for left of 6
        
        #update rifht of i, including i
        value = rightSizes.get(posleft,maxvalue)
        rightSizes[posleft] = min (value,posright-posleft + 1 )
        #update left of i, not including i
        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 = {}  #include start-range
    
        posleft = 0
        posright = 0
        currSum = 0
        while  posright < len(arr):
            currSum += arr[posright]
            if currSum  == target:
                self.updateArrays(leftSizes,rightSizes, posleft, posright, len(arr))
                #move pointers to the right
                posright +=1
                currSum -= arr[posleft]
                posleft +=1
            elif currSum  > target:
                #remove leftmost element 
                currSum =  currSum - arr[posright] - arr[posleft] 
                posleft +=1
            else: #currSum < target
                #include current element move right pointer
                posright +=1
        #print ('left', leftSizes)   
        #print('right', rightSizes)
        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)
        #print ('left', leftArray)
        #print ('right', rightArray)  
        #process hashmaps by i position
        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
            #print (i, leftSize, rigthSize)
            minSum = min(minSum, leftSize + rightSize)
        if minSum == 2*len(arr):
            minSum = -1
        return minSum
            
                

            
        
        
    def minSumOfLengthsx(self, arr: List[int], target: int) -> int:
        #two pointers 
        #loop until sum = target or > target
        #if greather than target, move posleft one to the right 

        #keep array of lenghts and get the samllet two (this can be optimized)
        #or get subarrays, even if they overlap, and then choose the smalles when overalp 
        
        posleft = 0
        posright = 0
        lengths = [] # keeping two smallest?
        currSum = 0
        while  posright < len(arr):
            currSum += arr[posright]
            #`print (posleft, posright, currSum)
            if currSum  == target:
                lengths.append(posright-posleft + 1)
                posright +=1
                posleft = posright
                currSum = 0
                #if posright < len(arr):
                #   currSum = arr[posright]
                
            elif currSum  > target:
                #remove leftmost element 
                currSum =  currSum - arr[posright] - arr[posleft] 
                posleft +=1
            else:
                #include current element move right pointer
                posright +=1
                #if posright < len(arr):
                #    currSum += arr[posright]
        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:
        
        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:
                
                # j is on the left
                # i is on the right
                j = prefix[curr - target]
                
                if j > -1:
                    # Update the ans, the current one and the non-overlapping best one
                    ans = min(ans, i - j + best_till[j])
                
                # update the shortest length until i
                best = min(best, i - j)
                
            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:
        record = collections.defaultdict()
        record[0] = 0
        l1 = l2 = float('Inf')
        tmp_sum = 0
        res = float('Inf')
        dp = [float('Inf') for _ in range(len(arr))]
        for i in range(len(arr)):
            tmp_sum += arr[i]
            if tmp_sum - target in record:
                dp[i] = i - record[tmp_sum - target] + 1
            record[tmp_sum] = i + 1
            if i>0:
                dp[i] = min(dp[i], dp[i-1])
        
        record.clear()
        tmp_sum = 0
        record[0] = len(arr)
        for i in range(len(arr)-1, 0, -1):
            tmp_sum += arr[i]
            if tmp_sum - target in record:
                res = min(res, dp[i-1] + record[tmp_sum - target] - i)
            record[tmp_sum] = i
            
        return res if res<float('Inf') else -1
        


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
        
        
        
        
        
        
        
        
#         prefix_sum = [0 for i in range(len(arr) + 1)]
#         for i in range(len(arr)):
#             prefix_sum[i+1] = prefix_sum[i] + arr[i]
            
#         prefix = [float('inf') for i in range(len(arr))]
#         suffix = [float('inf') for i in range(len(arr))]
        
#         for i in range(1, len(arr)):
#             # found = False
#             for j in range(i-1, -1, -1):
#                 if prefix_sum[i] - prefix_sum[j] == target:
#                     # found = True
#                     prefix[i] = i - j
#                     break
        
#         for i in range(len(arr) - 1, -1, -1):
#             # found = False
#             for j in range(i+1, len(arr) + 1):
#                 if prefix_sum[j] - prefix_sum[i] == target:
#                     # found = True
#                     suffix[i] = j - i
#                     break
                
#         for i in range(1, len(prefix)):
#             prefix[i] = min(prefix[i], prefix[i-1])
            
#         for i in range(len(suffix) - 2, -1, -1):
#             suffix[i] = min(suffix[i], suffix[i+1])
            
#         min_len = float('inf')
#         for i in range(len(arr)):
#             min_len = min(min_len, prefix[i] + suffix[i])
#         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
            
        #print(table)
        #print(dp1)
        
        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
        
        #print(table)
        #print(dp2)
    
        
        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
        # print(preCands)
        # print(sufCands)
        
        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]
        # print(prefixSum)
        # print(suffixSum)
        
        res = sys.maxsize
        for i in range(len(arr)):
            res = min(res, prefixSum[i] + suffixSum[i])
            
        return res if res != sys.maxsize else -1
                
        
        
#         t = 6
        
# idx         0 1 2 3 4 5 6 7 8
        
# arr         1 2 3 3 2 1 1 1 1
#                 3 3
#             1 2 3
#                   3 2 1
#                      2 1 1 1 1
        
# preSum      0 1 3 6 9 11 12 13 14 15
        
# preCands    M M 3 2 M 3 M M 5
# sufCands    3 M 2 3 5 M M M M
        
# prefix      M M M 3 2 2 2 2 2
# suffix      2 2 2 3 5 M M M M
        


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:
            #    print(\"found\",cumulative[i]-target,\"!\")
                l=i-d[cumulative[i]-target]
                best1=min(best1,l)
            
            forward_vals[i]=best1    
                
             #   print(\"the subarray with sum=target is\",(start+1,i))
            if (reverse_cumulative[i]-target) in dr:
                l=i-dr[reverse_cumulative[i]-target]
                best2=min(best2,l)
                
            backward_vals[i]=best2
                
            
            i+=1
       # print(cumulative,reverse_cumulative)
        #print(d,dr)
        #print(forward_vals,backward_vals)
        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
        #print(d)
        
        


class Solution:
  # 872 ms
  def minSumOfLengths(self, arr, target):
    result = inf = 2**31-1
    i = window = 0
    premin = [inf] * len(arr)

    # i: window start, j: window end
    for j, num in enumerate(arr):
      window += num
      while window > target:
        window -= arr[i]
        i += 1
      if window == target:
        # curr: length
        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:
        
        '''
        1 1 1 2 2 3 1 1 1 1 1  target : 5
        '''
        
        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


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):
            # print(c, target, target-c, h2idx)
            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])
            
# t = 7
# [ 2, 2, 3, 4, 3, 4]

    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
        print(cumsum)
        best_at_i = [INF] * len(arr)
        best = INF
        for idx,c in enumerate(cumsum):
            # print(c, target, target-c, h2idx)
            if c == target: 
                # print('sdfjsldfjksdl')
                # best = min(best, best_at_i[left-1] + idx+1)
                best_at_i[idx] = min(best_at_i[idx-1], idx+1)
            if (c-target) in h2idx:
                # print('fhgjdkg')
                left = h2idx[c-target]
                best = min(best, best_at_i[left] + idx - left)
                best_at_i[idx] = min(best_at_i[left], idx - left)
                # print(idx, left, best_at_i[left], best)
            h2idx[c] = idx
            best_at_i[idx] = min(best_at_i[idx-1], best_at_i[idx])
            
        print(best_at_i, h2idx)
        return best if best != INF else -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, target):
    inf = 2**31-1
    i, window, result = 0, 0, inf
    premin = [inf] * len(arr)

    # i: window start, j: window end
    for j, num in enumerate(arr):
      
      window += num
      while window > target:
        window -= arr[i]
        i += 1
      if window == target:
        # curr: length
       # print(premin, i, j)
        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:
        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])
                    # if q[0] > 0:
                    result = min(result, smallest[q[0]-1] + len(q))
            else:
                # if i > 0:
                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)
                # 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)
            # print(i, j, sm)
            
            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)
                # j -= 1
            i -= 1
        
        ans = math.inf
        # print(lans)
        # print(rans)
        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:
        # record the best at outcome at each index
        
        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:
                # shrink the window
                curr_sum -= arr[left]
                left += 1
                
            
            if curr_sum == target:
                # found subarray
                curr_len = right - left + 1
                prev_len = record.get(left - 1, sys.maxsize)
                record[right] = min(record.get(right - 1, sys.maxsize), curr_len)
                
                # update the result
                shortest = min(shortest, curr_len + prev_len)
            else:
                # keep looking
                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, target):
    result = inf = 2**31-1
    i, window = 0, 0
    premin = [inf] * len(arr)

    # i: window start, j: window end
    for j, num in enumerate(arr):
      
      window += num
      while window > target:
        window -= arr[i]
        i += 1
      if window == target:
        # curr: length
       # print(premin, i, j)
        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:
        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]
            else:                
                if 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[i] is the min len of subarr with sum in arr[:i+1]
        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
    
    # 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:
  # 872 ms
  def minSumOfLengths(self, arr, target):
    if len(arr) < 2: return -1
    if arr.count(target) >= 2: return 2
    result = inf = 2**31-1
    i = window = 0
    premin = [inf] * len(arr)

    # i: window start, j: window end
    for j, num in enumerate(arr):
      window += num
      while window > target:
        window -= arr[i]
        i += 1
      if window == target:
        # curr: length
        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:
        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 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:
                end=psum[csum-target]
                best=(min(best,i-end))
                if end>-1:
                    re=min(re,dp[end]+i-end)   
            dp[i]=best
        if re<100001:
            return re
        return -1
    
    # 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, target):
    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 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:
            #print(i,j, sum_)
            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] )
        '''
        for i in range(len(interval)):
            s, e, val = interval_val_sorted[i][0], interval_val_sorted[i][1], interval_val_sorted[i][2]
            ind = findCeil(e, interval)
            if ind == -1:
                continue
            val1 = ind[2]
            return val + val1
        '''
        print(interval_val_sorted )
        print(interval)
        i_ , j_, l_ = interval[0][0], interval[0][1], interval[0][2]
        #l_1 = 0
        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]
            #print(i_1, j_1)
            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_ = arr[i]
        sum_= 0
        j = 0
        while i < n and j < n:
    
            sum_+=arr[j]
            
            while j<n-1 and sum_ < target:
                j+=1
                #print(j)
                sum_+= arr[j]
                
            #print(\"B:\", i,j, sum_)  
            if sum_ == target:
                overlaps.append([i, j])
                
            sum_-=arr[i]
            sum_-=arr[j]
            i+=1
            #j+=1
            #print(\"A:\", i,j, sum_)
        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
        #print(overlaps)
        #print(starting)
        #print(length)
        #print(min_arr)
        min_arr = list(reversed(min_arr))
        for overlap in overlaps:
            s, e = overlap[0], overlap[1]
            indi = self.findCeil(e, starting)
            #print(\"s,e, indi\", s, e, indi)
            if indi == -1:
                continue
            min_length = min(min_length, e-s+1 + min_arr[indi])
            #print(min_length)
        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
        #print(shortestAt)
        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
        # print(mp)
        
        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[i] means the minimum length of the sub-array with sum equal to target from 0 to i
        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:
        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:
        n = len(arr)
        dp = [float('inf')]*(n+1)
        s, e = 0, 0
        total = 0
        while e < n:
            total += arr[e]
            e += 1
            while total > target:
                total -= arr[s]
                s += 1
            if total == target:
                dp[e] = e-s

        ans = float('inf')
        for i in range(1, n+1):
            if dp[i]<= i:
                ans = min(ans, dp[i-dp[i]]+dp[i])
            dp[i] = min(dp[i], dp[i-1])

        return ans if ans<float('inf') 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. for every i, find the minimum value of length of sub-array on the left or starting with i whose value is equal to target. Find another sub-array starting with i+1, whose sum is target. Update the result with the minimum value of the sum of both the sub-array. This is possible because all values are positive and the value of sum is strictly increasing, meaning arr[i]+target will always be on the right of i, and, if arr[i]+target exists, there will only be one answer (this condition also applies to arr[i]-target, there will only be one answer for each i if the answer exists, as the array is strictly increasing and there's no zeros) 
        
        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:
        # PreSum. for every i, find the minimum value of length of sub-array on the left or starting with i whose value is equal to target. Find another sub-array starting with i+1, whose sum is target. Update the result with the minimum value of the sum of both the sub-array. This is possible because all values are positive and the value of sum is strictly increasing, meaning arr[i]+target will always be on the right of i, and, if arr[i]+target exists, there will only be one answer (this condition also applies to arr[i]-target, there will only be one answer for each i if the answer exists, as the array is strictly increasing and there's no zeros) 
        # Again the array is strictly increasing, so at each i, there may exist one left solution including i and one right solution including i, compare those against all prior left solutions and all prior right solutions. Now, no need to compare right solution if there has never been a left solution.
        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]
            # compare current solution to hit curSum-target including i with all prior left solutions
            if curSum-target in preSum:
                lsize = min(lsize, i-preSum[curSum-target])
            # If left solution exists, compare current solution to hit curSum+target including i with all prior right solutions
            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:
        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

#https://leetcode-cn.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/solution/biao-zhun-de-dong-tai-gui-hua-zhu-xing-jiang-jie-b/


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]
            # find min length whose right end point is i 
            if prefix_sum - target in prefix_sum2_idx:
                l_min_len = min(l_min_len, i - prefix_sum2_idx[prefix_sum - target])
            
            # find min length whose left start point is i + 1
            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]
        
        # arr is now prefix_sum
        
        index = {0: -1} # map prefix_sum -> index of that sum
        best_till = [float('inf')] * len(arr) # best_till[i] is best answer up till that
        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
        
        
'''
target=7
[1,6,1]

arr=[1,7,8]
index { 0->-1, 1->0, }
best_till= [inf, 2, 2]
res = inf

i=2, val=8
start_of_window = 0
length = 2

'''

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):
            #s[end] - s[start] = target
            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:
        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):
#             ans = min(ans, left[i] + right[n-1-(i+1)])
#         return ans if ans < n+1 else -1
        
        
        # h = {0:-1}
        # preSum = [0 for i in range(n)]
        # for i in range(n):
        #     preSum[i] = preSum[i-1] + arr[i] if i > 0 else arr[0]
        #     h[preSum[i]] = i
        # left = [n+1 for i in range(n)]
        # ans = n+1
        # for i in range(n):
        #     if preSum[i]-target in h:
        #         left[i] = i-h[preSum[i]-target]
        #     if i > 0:
        #         left[i] = min(left[i-1], left[i])
        #     if left[i] < n+1 and preSum[i]+target in h:
        #         right = h[preSum[i]+target]-i
        #         ans = min(ans, left[i]+right)
        # return ans if ans < n+1 else -1
                
            
        h = {0:-1}
        preSum = 0
        for i in range(n):
            preSum = preSum + arr[i] if i > 0 else arr[0]
            h[preSum] = i
        ans = n+1
        left = n+1
        preSum = 0
        for i in range(n):
            preSum += arr[i]
            if preSum-target in h:
                left = min(left, i-h[preSum-target])
            if left < n+1 and preSum+target in h:
                right = h[preSum+target]-i
                ans = min(ans, left+right)
        return ans if ans < n+1 else -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:
        # They are all positive

        n = len(arr)
        # DP is shortest array up to i
        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]) # or 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
                # print(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
        # print(dp)
        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:
        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:
        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:
            #    dp[i]=1
            '''
                if prefxSum-arr[i] in dct:
                    start=dct[prefxSum-arr[i]]
                    if dp[start]!=float('inf'):
                        mn=min(mn, dp[start]+dp[i])
            '''   
            if prefxSum-target in dct:
                start=dct[prefxSum-target]
                #print(\"i: \",i,\", j: \",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]
        #print(dp)
        return mn if mn!=float('inf') else -1
        '''
        below brute force DOES NOT WORK
        idx=[]
        for i in range(0, len(arr)):
            for j in range(i, len(arr)):
                if sum(arr[i:(j+1)])==target:
                    idx.append([j-i+1,i, j])
        #print(idx)            
        if len(idx)<2:
            return -1
        idx=sorted(idx)
        #print(idx)
        
        a1=idx[0][0]
        L0, i,j=idx[0]
        for k in range(1, len(idx)):
            L, start, end=idx[k]
            #if not (start<=i<=end or start<=j<=end):
            if not (i<=start<=j or i<=end<=j):
                #idx.append([j-i+1,i, j])
                a2=end-start+1
                return a1+a2
                
        #return idx[0][0] + idx[1][0]
        return -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
        # print(indexes)
        # print(dp)
        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
        
        #print(prefixes)
        #print(suffixes)
        
        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


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 # Naturally impossible length. Will be updated if any possible case exist. Will tell when no possible case
        min_left = n + 1
        sum_left = 0
        s_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 *
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 = []
        # print(mapper)
        for i, a in enumerate(arr):
            cumu += a
            # print(cumu, cumu - target in mapper)
            if cumu - target in mapper:
                if l == None:
                    count += 1
                    l = i - mapper[cumu - target]
                    # print(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:
        # left to right, compute min length of subarray using elems from 0 up to and including i
        # right to left, compute min length of subarray using elems from i+1 to n-1
        # go thru array, pick i s.t. leftmin[i] + rightmin[i] is smallest
        
        n = len(arr)
        
        # compute left to right
        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
        

        # compute right to left
        curr_sum = 0
        curr_best = -1
        
        lo = hi = n-1
        rmin = [-1] # since lo is exclusive, rmin[n-1] should be -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]
        
        # print(lmin)
        # print(rmin)
        
        # compute best
        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:
        # O(n), Space: O(n)
        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]) # find previous (before l - 1) sub-arrays, avoid overlapping
                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
            
            
            
        
            
                    
                    
                    
        
        
        #[3,1,1,1,5,1,2,1]
        #3 4 5 6 11 12 14 15
        
       # 1 0 0 3 0 0.  2. 2 


from collections import deque
from itertools import accumulate

class Solution:
  def minSumOfLengths(self, arr: List[int], target: int) -> int:
    # TC: O(N), SC: O(N), prefix sum + deque
    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
    # min length beyond index i-th
    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)
            #print(i, temp_s)
            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) 
                    #print(\"found\", i, index, temp_s, best_till[i], res)
            else:
                if i >= 1:
                    best_till[i] = best_till[i - 1]
        #print(\"best_till\", best_till)
        return -1 if res == sys.maxsize else res
        


class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        
        # m[i]: min length and and in i, included
        
        ptr1, ptr2 = 0, 0  # both inclusive
        s = arr[0]  # cum sum
        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')
        # count=2
        l=0
        r=0
        window=0
        while l<=r and r<len(arr):
            
            window+=arr[r]
            while l<=r and window>target:
                # print(l,r)
                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
                
                
        
        
        
        
        
        
#         dp=[0 for i in range(len(arr)+1)]
        
#         currSum=0
#         l=[]
#         i=0
#         j=0
        
#         while i<=j and j<len(arr):
            
#             currSum=currSum+arr[j]
#             print(i,j,currSum)
#             if currSum==target or arr[j]==target:
#                 l.append(j-i+1)
#                 currSum=0
#                 j+=1
#                 i=j
                
#             elif currSum<target:
#                 currSum+=arr[j]
#                 j+=1
                
#             else:
#                 # print(\"h\",currSum)
#                 currSum=currSum-arr[i]
#                 # print(currSum,arr[i])
#                 i+=1
                
#         print(l)


import bisect

class Solution:
    def minSumOfLengths(self, arr, target):
        # inclusive, inclusive sliding window pointers
        lo = 0
        hi = 0
        cur = arr[0]

        # store (end, start) pairs of valid subarrays
        running_min = []

        ans = 1e9

        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 != 1e9 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:
        # 1. Iterate i: 0 ~ n-2
        #   1a. find min length to make target number in 0 ~ i
        #   1b. if found, see if possible to make target number with consequent numbers starting from i+1
        #   1c. if found, update min
        
        n = len(arr)
        best_to = [n + 1 for _ in range(n)]
        best_from = dict()
        min_total = n + 1 # Naturally impossible length. Will be updated if any possible case exist. Will tell when no possible case
        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])
        
#         for i in range(n - 1):
#             sum_left += arr[i]
#             if sum_left == target:
#                 # print(str(s_left) + '->' + str(e_left))
#                 best[s_left] = e_left - s_left + 1
#                 min_left = min(min_left, best[s_left])
#             elif sum_left > target:
#                 # Need to drop some numbers
#                 while s_left < e_left and sum_left > target:
#                     sum_left -= arr[s_left]
#                     s_left += 1
#                 if sum_left == target:
#                     min_left = min(min_left, e_left - s_left + 1)
#             # Skip if a subarray is not found on left
#             if min_left > n:
#                 continue
            
#             if i + 1 in 
#             sum_right = 0
#             for j in range(i + 1, n):
#                 sum_right += arr[j]
#                 if sum_right == target:
#                     min_total = min(min_total, min_left + j - i)
#                 elif sum_right > target:
#                     # Stop following as already exceeded
#                     break
        
        if min_total > n:
            return -1
        
        return min_total


class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        prefix = {0: -1}
        best_till = [math.inf] * len(arr)
        ans = best = math.inf
        curr = 0
        for i in range(len(arr)):
            curr += arr[i]
            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

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]
        #print(dp,dp2)
        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
        #min length of a valid subarray ends or before i.
        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:
        
        # subarr that has target sum
        len_to_start = collections.defaultdict(list)
        
        # find 
        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

        # find shortest
        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:
  # 864 ms
  def minSumOfLengths(self, arr, target):
    result = inf = 2**31-1
    i = window = count = 0
    # preMin: store previous shortest length
    preMin = [(-1, inf)]

    # i: window start, j: window end
    for j, num in enumerate(arr):
      window += num
      while window > target:
        window -= arr[i]
        i += 1
      if window == target:
        # curr: current length
        curr = j - i + 1
        n = 0 
        # find first minimal length n before window start i
        for index, length in preMin[::-1]:
          if index <= i-1: 
            n = length           
            break
        # update result if less    
        if result > curr + n: result = curr + n
            
        # update shortest length if less
        if curr < preMin[-1][-1]: preMin.append((j, curr))
          
        # early stopping if found two single targets
      #  if curr == 1: count += 1
      #  if count == 2: return 2

    return result if result < inf else -1

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:
  # 864 ms
  def minSumOfLengths(self, arr, target):
    result = inf = 2**31-1
    i = window = count = 0
    # preMin: store previous shortest length
    preMin = [(-1, inf)]

    # i: window start, j: window end
    for j, num in enumerate(arr):
      window += num
      while window > target:
        window -= arr[i]
        i += 1
      if window == target:
        # curr: current length
        curr = j - i + 1
        n = 0 
        # find first minimal length before window start i
        for index, length in preMin[::-1]:
          if index <= i-1: 
            n = length           
            break
        # update result if less    
        if result > curr + n: result = curr + n
            
        # update shortest length if less
        if curr < preMin[-1][-1]: preMin.append((j, curr))
          
        # early stopping if found two single targets
        if curr == 1: count += 1
        if count == 2: return 2

    return result if result < 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:
        n=len(arr)
        min_lens=[float('inf')]*n
        ans=float('inf')
        cur_sum=0
        min_len=float('inf')
        s=0
        
        for e in range(n):
            cur_sum+=arr[e]
            while cur_sum>target:
                cur_sum-=arr[s]
                s+=1
            if cur_sum==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(cur_len, min_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:
        # They are all positive

        n = len(arr)
        # DP is shortest array up to i
        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:
                print(start, end)
                ans = min(ans, end - start + 1 + dp[start-1]) # or start - 1
                dp[end] = min(dp[end-1], end - start + 1)
            else:
                dp[end] = dp[end-1]
                
        print(dp)
        return ans if ans != float('inf') else -1

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


import bisect, heapq

class Solution:
    def minSumOfLengths(self, arr, target):
        # inclusive, inclusive sliding window pointers
        lo = 0
        hi = 0
        cur = arr[0]

        # store (end, start) pairs of valid subarrays
        pairs = []
        
        running_min = []

        ans = 1e9

        while lo <= hi and hi < len(arr):
            # print(running_min)
            # print(lo, hi, cur)
            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
                        # print(\"Attempting to find %d... got %d\" % (lo, prev_index))
                        if 0 <= prev_index < len(running_min):
                            ans = min(ans, hi - lo + 1 + running_min[prev_index][1])

                    running_min.append((hi, best_range))
                    heapq.heappush(pairs, (hi, lo))

                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 != 1e9 else -1

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):
#             ans = min(ans, left[i] + right[n-1-(i+1)])
#         return ans if ans < n+1 else -1
        
        
        h = {0:-1}
        preSum = [0 for i in range(n)]
        for i in range(n):
            preSum[i] = preSum[i-1] + arr[i] if i > 0 else arr[0]
            h[preSum[i]] = i
        left = [n+1 for i in range(n)]
        ans = n+1
        for i in range(n):
            if preSum[i]-target in h:
                left[i] = i-h[preSum[i]-target]
            if i > 0:
                left[i] = min(left[i-1], left[i])
            if left[i] < n+1 and preSum[i]+target in h:
                right = h[preSum[i]+target]-i
                ans = min(ans, left[i]+right)
        return ans if ans < n+1 else -1
                
            
            


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


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
        
        # for i in range(l):
        #     if left[i] < l and right[i] < l:
        #         ans = min(ans, left[i] + right[i])
        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
        #print(left)
        
        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:
        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:
        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):        # t is the length of good subarrays until index i.
            # if t == float('inf'): continue
            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):
            # if (targetSum[i] > 0):
            minValue = min(targetSum[i], minValue)
            beforeSum[i] = minValue

        minValue = sys.maxsize
        for i in reversed(list(range(1, n))):
            # print(targetSum[i])
            startIndex = i - targetSum[i]
            if (startIndex >= 0):
                afterSum[startIndex] = min(afterSum[startIndex], targetSum[i])
                # print(f\"Setting aftersum[{startIndex}] = {afterSum[startIndex]}\")
            # minValue = min(targetSum[i], minValue)
            # afterSum[i - 1] = minValue
                
        # print(f\"targetSum = {targetSum}\")
        # print(f\"afterSum = {afterSum}\")
        # print(f\"beforeSum = {beforeSum}\")
        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]

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
        print(left)
        
        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:
        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
        
        for i in range(l):
            if left[i] < l and right[i] < l:
                ans = min(ans, left[i] + right[i])
        
        if ans < l + 1:
            return ans
        
        return -1