Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.
A subarray of an array is a consecutive sequence of zero or more values taken out of that array.
Return the maximum length of a subarray with positive product.
 
Example 1:
Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:
Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.
Example 3:
Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

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

Example 5:
Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4

 
Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		maxx = 0
		nums.append(0)
		i = -1
		minusarr = []
		for (j, n) in enumerate(nums):
			if n == 0:
				tot = j - i - 1
				if not minusarr or len(minusarr) % 2 == 0:
					maxx = max(maxx, tot)
				else:
					left = minusarr[0] - i
					right = j - minusarr[-1]
					maxx = max(maxx, tot - min(left, right))
				minusarr = []
				i = j
			elif n < 0:
				minusarr.append(j)
		return maxx


class Solution:

	def getMaxLen(self, a: List[int], having_zero=True) -> int:
		if not a:
			return 0
		if having_zero:
			zeros = [i for (i, x) in enumerate(a) if x == 0]
			(ans, prev) = (-float('inf'), 0)
			for i in zeros:
				ans = max(ans, self.getMaxLen(a[prev:i], False))
				prev = i + 1
			ans = max(ans, self.getMaxLen(a[prev:], False))
			return ans
		negs = [i for (i, x) in enumerate(a) if x < 0]
		if len(negs) % 2 == 0:
			return len(a)
		return max(negs[-1], len(a) - negs[0] - 1)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		l = len(nums)
		start = 0
		subArrays = []
		for i in range(l):
			if nums[i] == 0:
				subArrays.append(self.findOptimal(nums[start:i]))
				start = i + 1
				end = i + 1
		subArrays.append(self.findOptimal(nums[start:l]))
		return max(subArrays)

	def findOptimal(self, nums: List[int]) -> int:
		if not nums:
			return 0
		negs = 0
		l = 0
		for i in nums:
			l += 1
			if i < 0:
				negs += 1
		if negs % 2 == 0:
			return l
		else:
			i = 0
			j = l - 1
			while i < j:
				if nums[i] < 0 or nums[j] < 0:
					return l - 1
				i += 1
				j -= 1
				l -= 1
		return 0


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		pos_p = 0
		neg_p = 0
		(pos, neg) = (0, 0)
		result = 0
		for i in range(len(nums)):
			(pos_p, neg_p) = (pos, neg)
			if nums[i] > 0:
				pos = 1 + pos_p
				neg = 1 + neg_p if neg_p > 0 else 0
			elif nums[i] < 0:
				pos = 1 + neg_p if neg_p > 0 else 0
				neg = 1 + pos_p if pos_p > 0 else 1
			else:
				(pos, neg) = (0, 0)
			result = max(result, pos)
		return result


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		last = {1: -1}
		pro = 1
		ans = 0
		for (i, c) in enumerate(nums):
			pro = c * pro / abs(pro) if pro != 0 else 0
			if pro > 0:
				ans = max(i - last[1], ans)
			elif pro < 0:
				if -1 in last:
					ans = max(ans, i - last[-1])
				else:
					last[-1] = i
			elif pro == 0:
				pro = 1
				last = {}
				last[1] = i
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		dp = [[0] * (n + 1) for i in range(2)]
		for (i, x) in enumerate(nums):
			if x > 0:
				dp[0][i + 1] = dp[0][i] + 1
				if dp[1][i] > 0:
					dp[1][i + 1] = dp[1][i] + 1
			elif x < 0:
				if dp[1][i] > 0:
					dp[0][i + 1] = dp[1][i] + 1
				dp[1][i + 1] = dp[0][i] + 1
			else:
				dp[0][i + 1] = dp[1][i + 1] = 0
		return max(dp[0])


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		(pos, neg) = (0, 0)
		[0, 1, -2, -3, -4]
		if nums[0] > 0:
			pos = 1
		if nums[0] < 0:
			neg = 1
		ans = pos
		for i in range(1, n):
			if nums[i] > 0:
				pos = 1 + pos
				neg = 1 + neg if neg > 0 else 0
			elif nums[i] < 0:
				(pre_pos, pre_neg) = (pos, neg)
				pos = 1 + pre_neg if pre_neg > 0 else 0
				neg = 1 + pre_pos
			else:
				(pos, neg) = (0, 0)
			ans = max(ans, pos)
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(plus, minus, res, c) = (0, -1, 0, 0)
		for i in range(0, len(nums)):
			if nums[i] == 0:
				if c % 2 == 1:
					res = max(res, minus)
				else:
					res = max(res, max(plus, minus))
				(plus, minus, c) = (0, -1, 0)
			elif nums[i] > 0:
				if minus != -1:
					minus += 1
				plus += 1
			else:
				c += 1
				minus += 1
				if c % 2 == 1:
					res = max(res, max(minus, plus))
				plus += 1
		if c % 2 == 1:
			res = max(res, minus)
		else:
			res = max(res, max(plus, minus))
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		(pos, neg) = ([0] * n, [0] * n)
		if nums[0] > 0:
			pos[0] = 1
		if nums[0] < 0:
			neg[0] = 1
		ans = pos[0]
		for i in range(1, n):
			if nums[i] > 0:
				pos[i] = 1 + pos[i - 1]
				neg[i] = 1 + neg[i - 1] if neg[i - 1] > 0 else 0
			elif nums[i] < 0:
				pos[i] = 1 + neg[i - 1] if neg[i - 1] > 0 else 0
				neg[i] = 1 + pos[i - 1]
			ans = max(ans, pos[i])
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def solve(nums):
			cnt = 0
			for n in nums:
				if n < 0:
					cnt += 1
			if cnt % 2 == 0:
				return len(nums)
			for i in range(len(nums)):
				if nums[i] < 0:
					first = i
					break
			for i in range(len(nums) - 1, -1, -1):
				if nums[i] < 0:
					last = i
					break
			return max(last, len(nums) - first - 1)
		l = 0
		ans = 0
		nums.append(0)
		for r in range(len(nums)):
			if nums[r] == 0:
				cur = solve(nums[l:r])
				ans = max(ans, cur)
				l = r + 1
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		@lru_cache(None)
		def pos_helper(len):
			if len == 0:
				return 0
			if len == 1:
				return 1 if nums[0] > 0 else 0
			if nums[len - 1] > 0:
				return pos_helper(len - 1) + 1
			if nums[len - 1] == 0:
				return 0
			if nums[len - 1] < 0:
				return neg_helper(len - 1) + 1 if neg_helper(len - 1) != 0 else 0

		@lru_cache(None)
		def neg_helper(len):
			if len == 0:
				return 0
			if len == 1:
				return 1 if nums[0] < 0 else 0
			if nums[len - 1] > 0:
				return neg_helper(len - 1) + 1 if neg_helper(len - 1) > 0 else 0
			if nums[len - 1] == 0:
				return 0
			if nums[len - 1] < 0:
				return pos_helper(len - 1) + 1
		res = 0
		for i in range(0, len(nums) + 1):
			res = max(res, pos_helper(i))
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		maxlen = 0
		curlen = 0
		tmplen = 0
		even = True
		for i in nums:
			if i == 0:
				if tmplen != curlen:
					maxlen = max(maxlen, tmplen - curlen - 1)
				maxlen = max(maxlen, curlen)
				curlen = 0
				tmplen = 0
				even = True
				continue
			tmplen += 1
			if i < 0:
				even = not even
				if even == True:
					curlen = tmplen
			if i > 0 and even == True:
				curlen += 1
		if tmplen != curlen:
			maxlen = max(maxlen, tmplen - curlen - 1)
		maxlen = max(maxlen, curlen)
		curlen = 0
		tmplen = 0
		even = True
		for i in reversed(nums):
			if i == 0:
				if tmplen != curlen:
					maxlen = max(maxlen, tmplen - curlen - 1)
				maxlen = max(maxlen, curlen)
				curlen = 0
				tmplen = 0
				even = True
				continue
			tmplen += 1
			if i < 0:
				even = not even
				if even == True:
					curlen = tmplen
			if i > 0 and even == True:
				curlen += 1
		if tmplen != curlen:
			maxlen = max(maxlen, tmplen - curlen - 1)
		maxlen = max(maxlen, curlen)
		return maxlen


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		result = 0
		negativeIndices = []
		currentProduct = 1
		startIndex = 0
		for (index, number) in enumerate(nums):
			if number == 0:
				negativeIndices = []
				currentProduct = 1
				startIndex = index + 1
				continue
			if number * currentProduct > 0:
				result = max(result, index - startIndex + 1)
				currentProduct = 1
			else:
				if len(negativeIndices) != 0:
					result = max(result, index - negativeIndices[0])
				currentProduct = -1
			if number < 0 and len(negativeIndices) == 0:
				negativeIndices.append(index)
		return result


class Solution:

	def getMaxLen(self, A: List[int], cnt=0, best=0) -> int:
		A.append(0)
		N = len(A)
		i = 0
		j = 0
		while i < N:
			while j < N and (not A[j]):
				while i < j:
					cnt = cnt - 1 if A[i] < 0 else cnt
					i += 1
					best = best if cnt & 1 else max(best, j - i)
				i = j + 1
				j = j + 1
			while j < N and A[j]:
				cnt = cnt + 1 if A[j] < 0 else cnt
				j += 1
				best = best if cnt & 1 else max(best, j - i)
		return best


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		pos = 0
		neg = 0
		negIndex = 0
		res = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				pos = 0
				neg = 0
			elif nums[i] > 0:
				pos += 1
			else:
				neg += 1
				if neg == 1:
					negIndex = i
			if neg % 2 == 0:
				res = max(res, pos + neg)
			else:
				res = max(res, i - negIndex)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		pointer1 = 0
		pointer2 = 0
		res = 0
		while pointer1 < len(nums):
			if nums[pointer1] == 0:
				pointer1 += 1
				continue
			pointer2 = pointer1
			count = 0
			start = 0
			end = 0
			while pointer2 < len(nums) and nums[pointer2] != 0:
				if nums[pointer2] < 0:
					count += 1
					if count == 1:
						start = pointer2
					end = pointer2
				pointer2 += 1
			if count % 2 == 0:
				res = max(res, pointer2 - pointer1)
			else:
				res = max(res, end - pointer1, pointer2 - start - 1)
			pointer1 = pointer2
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if not nums:
			return 0
		n = len(nums)
		negNum = 0
		firstNegIdx = -1
		zeroPos = -1
		res = 0
		for (i, num) in enumerate(nums):
			if num < 0:
				negNum += 1
				if firstNegIdx < 0:
					firstNegIdx = i
			if num == 0:
				negNum = 0
				firstNegIdx = -1
				zeroPos = i
			elif negNum % 2 == 0:
				res = max(res, i - zeroPos)
			else:
				res = max(res, i - firstNegIdx)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(res, pos, neg) = (0, 0, 0)
		for num in nums:
			if num == 0:
				(pos, neg) = (0, 0)
			elif num > 0:
				if neg != 0:
					(neg, pos) = (neg + 1, pos + 1)
				else:
					(neg, pos) = (0, pos + 1)
			elif neg != 0:
				(pos, neg) = (neg + 1, pos + 1)
			else:
				(neg, pos) = (pos + 1, 0)
			res = max(res, pos)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ans = 0
		mn = 0
		mp = 0
		for i in nums:
			if i == 0:
				(mn, mp) = (0, 0)
			elif i > 0:
				mp += 1
				if mn != 0:
					mn += 1
				else:
					mn = 0
			else:
				omn = mn
				mn = mp + 1
				if omn != 0:
					mp = omn + 1
				else:
					mp = 0
			ans = max(mp, ans)
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		pos_num = neg_num = res = 0
		for (i, num) in enumerate(nums):
			if num == 0:
				pos_num = neg_num = 0
			elif num > 0:
				neg_num = neg_num + 1 if neg_num else 0
				pos_num += 1
			else:
				cur_pos = pos_num
				pos_num = neg_num + 1 if neg_num else 0
				neg_num = cur_pos + 1
			res = max(res, pos_num)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def helper(arr):
			inds = []
			for (i, num) in enumerate(arr):
				if num < 0:
					inds.append(i)
			if len(inds) % 2 == 0:
				return len(arr)
			else:
				first = max(inds[0], len(arr) - inds[0] - 1)
				second = max(inds[-1], len(arr) - inds[-1] - 1)
				return max(first, second)
		temp = []
		for (i, num) in enumerate(nums):
			if num == 0:
				temp.append(i)
		pos = []
		if temp:
			if nums[:temp[0]]:
				pos.append(nums[:temp[0]])
			for i in range(0, len(temp) - 1):
				pos.append(nums[temp[i] + 1:temp[i + 1]])
			if nums[temp[-1] + 1:]:
				pos.append(nums[temp[-1] + 1:])
		else:
			pos.append(nums)
		ans = 0
		for arr in pos:
			ans = max(ans, helper(arr))
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		lists = [[]]
		negative = [[]]
		index = 0
		for num in nums:
			if num == 0:
				index = 0
				negative.append([])
				lists.append([])
			else:
				if num < 0:
					negative[-1].append(index)
				lists[-1].append(num)
				index += 1
		max_len = 0
		for (l, neg) in zip(lists, negative):
			if len(neg) % 2 == 1:
				dist = min(neg[0] + 1, len(l) - neg[-1])
			else:
				dist = 0
			max_len = max(len(l) - dist, max_len)
		return max_len


import copy
import math

class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(positive, negative) = (0, 0)
		length = 0
		for n in nums:
			if n == 0:
				(positive, negative) = (0, 0)
			elif n > 0:
				if negative > 0:
					(positive, negative) = (positive + 1, negative + 1)
				else:
					(positive, negative) = (positive + 1, 0)
			elif negative > 0:
				(positive, negative) = (negative + 1, positive + 1)
			else:
				(positive, negative) = (0, positive + 1)
			length = max(length, positive)
		return length


import numpy as np

class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if len(nums) == 0:
			return 0
		if len(nums) == 1:
			return 1 if nums[0] > 0 else 0
		St = [i for (i, j) in enumerate(nums) if i == 0 and j != 0 or (nums[i - 1] == 0 and j != 0)]
		if len(St) == 0:
			return 0
		Ed = [i for (i, j) in enumerate(nums) if i == len(nums) - 1 and j != 0 or (i < len(nums) - 1 and nums[i + 1] == 0 and (j != 0))]
		Sta = np.array(St)
		Eda = np.array(Ed)
		Lns = (-(Eda - Sta + 1)).argsort()
		k = 0
		mxLen = 0
		while k < len(Lns):
			nums1 = nums[St[Lns[k]]:Ed[Lns[k]] + 1]
			if len(nums1) == mxLen:
				return mxLen
			ni = [i for (i, j) in enumerate(nums1) if j < 0]
			if len(ni) == 0 or len(ni) % 2 == 0:
				mxLen = max(mxLen, len(nums1))
			else:
				mn = min(ni)
				mx = max(ni)
				mxLen = max(mxLen, mn, len(nums1) - mn - 1, mx, len(nums1) - mx - 1)
			k = k + 1
		return mxLen


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		p = 1
		j = None
		k = -1
		m = 0
		for (i, n) in enumerate(nums):
			if not n:
				p = 1
				j = None
				k = i
			else:
				if n < 0:
					p *= -1
				elif not n:
					p = 0
				if p > 0:
					m = max(m, i - k)
				elif p < 0:
					if j is None:
						j = i
					else:
						m = max(m, i - j)
		return m


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		p = 0
		n = 0
		longest_p = 0
		for num in nums:
			longest_p = max(longest_p, p)
			if num == 0:
				p = 0
				n = 0
			elif num > 0:
				prev_p = p
				prev_n = n
				p = prev_p + 1
				if prev_n > 0:
					n = prev_n + 1
				else:
					n = 0
			elif num < 0:
				prev_p = p
				prev_n = n
				n = prev_p + 1
				if prev_n > 0:
					p = prev_n + 1
				else:
					p = 0
		longest_p = max(longest_p, p)
		return longest_p


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		if n == 1:
			return 1 if nums[0] > 0 else 0
		p1 = p2 = 0
		answer = 0
		curr_len = 0
		neg_indx = deque([])
		while p2 < n:
			num = nums[p2]
			if num == 0:
				answer = max(answer, curr_len)
				curr_len = 0
				p2 += 1
				p1 = p2
				neg_indx = deque([])
			elif num > 0:
				curr_len += 1
				answer = max(answer, curr_len)
				p2 += 1
			else:
				neg_indx.append(p2)
				j = p2 + 1
				found = False
				while j < n:
					num2 = nums[j]
					if num2 <= 0:
						if num2 < 0:
							neg_indx.append(j)
							found = True
						break
					j += 1
				if found:
					curr_len += j - p2 + 1
					answer = max(answer, curr_len)
					if j == n - 1:
						return answer
					else:
						p2 = j + 1
				else:
					first_neg = neg_indx.popleft()
					while p1 <= first_neg:
						p1 += 1
						curr_len -= 1
					if p1 > p2:
						p2 = p1
						answer = max(answer, curr_len)
						curr_len = 0
					else:
						curr_len += 1
						p2 += 1
					continue
		return answer


class Solution:

	def getMaxLen(self, nums):
		if len(nums) == 0:
			return True
		result = 0
		count = 0
		zero_marker = -1
		negative_marker = -1
		for i in range(len(nums)):
			if nums[i] == 0:
				zero_marker = i
				count = 0
				negative_marker = -1
			else:
				if nums[i] < 0:
					count += 1
					if negative_marker == -1:
						negative_marker = i
				if count % 2 == 0:
					result = max(result, i - zero_marker)
				else:
					result = max(result, i - negative_marker)
		return result


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)

		def get_val(nums):
			if len(nums) == 0:
				return 0
			products = [1]
			product = 1
			length = len(nums)
			for i in range(length):
				product *= nums[i]
				products.append(product)
			for j in range(length, 0, -1):
				for k in range(length - j + 1):
					value = products[k + j] // products[k]
					if value > 0:
						return j
			return 0
		index = 0
		maximum = 0
		for i in range(n):
			if nums[i] == 0:
				if i == index:
					index += 1
					continue
				value = get_val(nums[index:i])
				if value > maximum:
					maximum = value
				index = i + 1
			elif nums[i] > 0:
				nums[i] = 1
			else:
				nums[i] = -1
		value = get_val(nums[index:n])
		if value > maximum:
			maximum = value
		return maximum


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		maxl = 0
		pos = 0
		neg = 0
		for n in nums:
			if n == 0:
				(pos, neg) = (0, 0)
			elif n > 0:
				pos += 1
				neg = neg + 1 if neg != 0 else 0
			elif n < 0:
				oldneg = neg
				neg = pos + 1
				pos = oldneg + 1 if oldneg > 0 else 0
			maxl = max(maxl, pos)
		return maxl


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def oddMinus(ls):
			ret = 0
			for i in range(len(ls)):
				if ls[i] < 0:
					ret = max(max(ret, i), len(ls) - 1 - i)
			return ret

		def getLen(ls):
			minus = 0
			for i in ls:
				if i < 0:
					minus += 1
			if minus % 2 == 0:
				return len(ls)
			else:
				return oddMinus(ls)
		s = []
		sub = []
		for i in nums:
			if i == 0:
				s.append(sub)
				sub = []
			else:
				sub.append(i)
		s.append(sub)
		res = 0
		for ls in s:
			res = max(res, getLen(ls))
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ret = 0
		(pos, neg) = (-1, None)
		curr = 0
		for (i, n) in enumerate(nums):
			if n == 0:
				(pos, neg) = (i, None)
				curr = 0
			else:
				if n < 0:
					curr = 1 - curr
				if curr == 0:
					ret = max(ret, i - pos)
				if curr == 1:
					if neg is not None:
						ret = max(ret, i - neg)
					else:
						neg = i
		return ret


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		nums.append(0)
		start = -1
		i = 0
		firstn = -1
		maxl = 0
		nneg = 0
		while i < len(nums):
			if nums[i] < 0:
				nneg += 1
				if firstn < 0:
					firstn = i
				lastn = i
			elif nums[i] == 0:
				if nneg % 2 == 0:
					maxl = max(maxl, i - start - 1)
				else:
					maxl = max([maxl, lastn - start - 1, i - firstn - 1])
				start = i
				nneg = 0
				firstn = -1
			i += 1
		return maxl


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def dfs(start):
			i = start
			if i >= len(nums):
				return 0
			ret = 0
			stack = []
			while i < len(nums):
				if nums[i] == 0:
					break
				elif nums[i] < 0:
					stack.append(i)
				i += 1
			if len(stack) % 2 == 0:
				ret = i - start
			else:
				ret = max(i - 1 - stack[0], stack[-1] - start)
			return max(ret, dfs(i + 1))
		return dfs(0)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def solve(arr):
			maxy = 0
			count = 0
			for i in j:
				if i < 0:
					count += 1
			if count % 2 == 0:
				maxy = max(maxy, len(j))
			else:
				for i in range(len(j)):
					if j[i] < 0:
						m1 = i
						m2 = len(j) - m1 - 1
						m3 = max(m1, m2)
						maxy = max(maxy, m3)
						break
				for i in range(len(j) - 1, -1, -1):
					if j[i] < 0:
						m1 = i
						m2 = len(j) - m1 - 1
						m3 = max(m1, m2)
						maxy = max(maxy, m3)
						break
			return maxy
		res = []
		maxy = 0
		flag = 1
		i = 0
		for j in range(i, len(nums)):
			if nums[j] == 0:
				res.append(nums[i:j])
				i = j + 1
				flag = 0
		if flag == 1:
			res.append(nums)
		elif flag == 0:
			res.append(nums[i:])
		nums = res
		for j in nums:
			maxy = max(maxy, solve(j))
		return maxy


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		firstNeg = -1
		zeroPos = -1
		cnt = 0
		ret = 0
		for (i, n) in enumerate(nums):
			if n < 0:
				cnt += 1
				if firstNeg == -1:
					firstNeg = i
			elif not n:
				(firstNeg, cnt) = (-1, 0)
				zeroPos = i
			if cnt % 2:
				ret = max(ret, i - firstNeg)
			else:
				ret = max(ret, i - zeroPos)
		return ret


class Solution:

	def getMaxLen(self, arr: List[int]) -> int:
		i = 0
		while i <= len(arr) - 1 and arr[i] == 0:
			i += 1
		arr = arr[i:]
		if len(arr) == 0:
			return 0
		i = len(arr) - 1
		while i <= len(arr) - 1 and arr[i] == 0:
			i -= 1
		arr = arr[:i + 1]
		if len(arr) == 0:
			return 0
		array = []
		low = 0
		high = 0
		ans = []
		while low < len(arr):
			while high < len(arr) and arr[high] != 0:
				high += 1
			if high == len(arr) - 1:
				break
			else:
				array.append(arr[low:high])
				while high < len(arr) and arr[high] == 0:
					high += 1
				low = high
		for a in array:
			if len(a) == 0:
				continue
			else:
				total = 0
				first = 0
				last = 0
				for i in range(len(a)):
					if a[i] < 0:
						total += 1
				if total % 2 == 0:
					ans.append(len(a))
				else:
					i = 0
					while a[i] > 0:
						i += 1
					first = len(a) - (i + 1)
					i = len(a) - 1
					while a[i] > 0:
						i -= 1
					last = i
				ans.append(max(first, last))
		ma = 0
		for i in ans:
			if i > ma:
				ma = i
		return ma


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		out = 0
		first = -1
		last = -1
		negs = 0
		start = 0
		for (i, num) in enumerate(nums):
			if num == 0:
				if negs % 2 == 0:
					new_max = i - start
				else:
					new_max = max(i - first - 1, last - start)
				out = max(out, new_max)
				first = -1
				last = -1
				negs = 0
				start = i + 1
			if num < 0:
				negs += 1
				if first == -1:
					first = i
				last = i
		i += 1
		if negs % 2 == 0:
			new_max = i - start
		else:
			new_max = max(i - first - 1, last - start)
		out = max(out, new_max)
		return out


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = [[0 for i in range(2)] for j in range(len(nums) + 1)]
		res = 0
		for (i, num) in enumerate(nums):
			if num == 0:
				dp[i + 1][0] = dp[num][1] = 0
			elif num > 0:
				dp[i + 1][0] = dp[i][0] + 1
				dp[i + 1][1] = dp[i][1] + 1 if dp[i][1] else 0
			else:
				dp[i + 1][0] = dp[i][1] + 1 if dp[i][1] else 0
				dp[i + 1][1] = dp[i][0] + 1
			res = max(res, dp[i + 1][0])
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ans = 0
		neg = 0
		(lo, hi) = (0, -1)
		for (i, num) in enumerate(nums):
			if num == 0:
				lo = i + 1
				neg = 0
			elif num < 0:
				neg += 1
			hi = i
			if neg % 2 == 0:
				ans = max(ans, hi - lo + 1)
		neg = 0
		nums = nums[::-1]
		(lo, hi) = (0, -1)
		for (i, num) in enumerate(nums):
			if num == 0:
				lo = i + 1
				neg = 0
			elif num < 0:
				neg += 1
			hi = i
			if neg % 2 == 0:
				ans = max(ans, hi - lo + 1)
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = [0 for _ in range(2)]
		res = 0
		if nums[0] > 0:
			dp[0] = 1
			res = 1
		if nums[0] < 0:
			dp[1] = 1
		for i in range(1, len(nums)):
			cur = nums[i]
			tmp = [0 for _ in range(2)]
			if cur > 0:
				tmp[0] = dp[0] + 1
				if dp[1] > 0:
					tmp[1] = dp[1] + 1
			if cur < 0:
				tmp[1] = dp[0] + 1
				if dp[1] > 0:
					tmp[0] = dp[1] + 1
			res = max(res, tmp[0])
			dp = tmp
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		positives = 0
		negatives = 0
		output = 0
		for i in range(len(nums)):
			if nums[i] > 0:
				positives += 1
				if negatives > 0:
					negatives += 1
			elif nums[i] < 0:
				if negatives > 0:
					tmp = positives
					positives = negatives + 1
					negatives = tmp + 1
				else:
					negatives = positives + 1
					positives = 0
			else:
				positives = 0
				negatives = 0
			output = max(output, positives)
		return output


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		neg = pos = 0
		ret = 0
		end = start = 0
		while end < len(nums):
			start = end
			while end < len(nums) and nums[end]:
				if nums[end] < 0:
					neg += 1
				if nums[end] > 0:
					pos += 1
				if neg % 2 == 0:
					ret = max(ret, end - start + 1)
					print(ret)
				end += 1
			while neg % 2:
				if nums[start] < 0:
					neg -= 1
					ret = max(ret, end - start - 1)
				start += 1
			neg = pos = 0
			while end < len(nums) and nums[end] == 0:
				end += 1
		return ret


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		pos_l = 0
		neg_l = 0
		best = 0
		for n in nums:
			if n == 0:
				pos_l = 0
				neg_l = 0
			elif n > 0:
				pos_l += 1
				if neg_l > 0:
					neg_l += 1
			elif neg_l == 0 and pos_l == 0:
				neg_l = 1
			elif neg_l > 0 and pos_l > 0:
				(pos_l, neg_l) = (neg_l + 1, pos_l + 1)
			elif neg_l > 0:
				pos_l = neg_l + 1
				neg_l = 1
			elif pos_l > 0:
				neg_l = pos_l + 1
				pos_l = 0
			best = max(best, pos_l)
		return best


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		cn = 0
		cp = 0
		f = 0
		n = len(nums)
		pz = -1
		ans = 0
		for i in range(n):
			if nums[i] < 0:
				if f == 0:
					fn = ln = i
				else:
					ln = i
				cn += 1
				f = 1
			elif nums[i] > 0:
				cp += 1
			else:
				if cn % 2 == 0:
					ans = max(ans, cn + cp)
				else:
					z = cn + cp - min(i - ln, fn - pz)
					ans = max(ans, z)
				f = 0
				cn = 0
				cp = 0
				pz = i
		if cn % 2 == 0:
			ans = max(ans, cn + cp)
		else:
			z = cn + cp - min(n - ln, fn - pz)
			ans = max(ans, z)
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		pos = 0
		neg = 0
		max_pos = 0
		curr = True
		for i in range(len(nums)):
			if nums[i] > 0:
				pos += 1
				if neg != 0:
					neg += 1
			elif nums[i] < 0:
				old_pos = pos
				if neg != 0:
					pos = neg + 1
				else:
					pos = 0
				neg = old_pos + 1
			else:
				neg = 0
				pos = 0
			max_pos = max(pos, max_pos)
		return max_pos


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp_pos = [0] * (len(nums) + 1)
		dp_neg = [0] * (len(nums) + 1)
		for i in range(len(nums)):
			if nums[i] > 0:
				dp_pos[i + 1] = dp_pos[i] + 1
				if dp_neg[i] == 0:
					dp_neg[i + 1] = 0
				else:
					dp_neg[i + 1] = dp_neg[i] + 1
			elif nums[i] < 0:
				dp_neg[i + 1] = dp_pos[i] + 1
				if dp_neg[i] == 0:
					dp_pos[i + 1] = 0
				else:
					dp_pos[i + 1] = dp_neg[i] + 1
		return max(dp_pos)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		from collections import defaultdict
		nums1 = []
		for i in nums:
			if i > 0:
				nums1.append(1)
			elif i < 0:
				nums1.append(-1)
			else:
				nums1.append(0)
		pre_arr = [0] * len(nums1)
		rem = []
		for i in range(len(nums1)):
			if i == 0:
				pre_arr[i] = nums1[i]
			elif pre_arr[i - 1] != 0:
				pre_arr[i] = nums1[i] * pre_arr[i - 1]
			else:
				pre_arr[i] = nums1[i]
		a1 = max(nums)
		if a1 > 0:
			m1 = 1
		else:
			m1 = 0
		Dict = defaultdict(int)
		start = 0
		for i in range(len(pre_arr)):
			if pre_arr[i] > 0:
				m1 = max(m1, i - Dict[1] + 1)
			elif pre_arr[i] == 0:
				Dict[1] = i + 1
		Dict1 = defaultdict(list)
		m2 = 0
		for i in range(len(pre_arr)):
			if pre_arr[i] < 0:
				Dict1[-1].append(i)
			elif pre_arr[i] == 0:
				if len(Dict1[-1]) >= 2:
					m2 = max(m2, Dict1[-1][-1] - Dict1[-1][0])
				Dict1.clear()
		if len(Dict1[-1]) >= 2:
			m2 = max(m2, Dict1[-1][-1] - Dict1[-1][0])
		return max(m1, m2)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		res = 0
		prod = 1
		p_start = -1
		n_start = 10 ** 6
		for i in range(n):
			if nums[i] == 0:
				p_start = i
				n_start = 10 ** 6
				prod = 1
				continue
			elif nums[i] < 0:
				prod = -prod
				if n_start == 10 ** 6:
					n_start = i
			res = max(res, i - p_start) if prod > 0 else max(res, i - n_start)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		neg = pos = max_len = 0
		fneg = lneg = -1
		beg = -1
		for (i, n) in enumerate(nums):
			if n < 0:
				neg += 1
				if fneg == -1:
					fneg = lneg = i
				else:
					lneg = i
			elif n > 0:
				pos += 1
			else:
				if neg % 2 == 0:
					max_len = max(max_len, neg + pos)
				else:
					max_len = max(max_len, max(lneg - beg - 1, i - fneg - 1))
					print((i, fneg, lneg, beg))
				neg = pos = 0
				fneg = lneg = -1
				beg = i
		if neg % 2 == 0:
			max_len = max(max_len, neg + pos)
		else:
			max_len = max(max_len, max(i - fneg, lneg - beg - 1))
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		v = {(0, 0): -1}
		neg = 0
		zero = 0
		maxlen = 0
		for (i, num) in enumerate(nums):
			if num < 0:
				neg = 1 - neg
			if num == 0:
				zero += 1
			if (neg, zero) not in v:
				v[neg, zero] = i
			else:
				maxlen = max(maxlen, i - v[neg, zero])
		return maxlen


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		res = 0
		(dp_po, dp_ne) = ([0] * (len(nums) + 1), [0] * (len(nums) + 1))
		for (i, value) in enumerate(nums):
			if value == 0:
				dp_po[i + 1] = 0
				dp_ne[i + 1] = 0
			elif value > 0:
				dp_po[i + 1] = dp_po[i] + 1
				if dp_ne[i] > 0:
					dp_ne[i + 1] = dp_ne[i] + 1
			else:
				dp_ne[i + 1] = dp_po[i] + 1
				if dp_ne[i] > 0:
					dp_po[i + 1] = dp_ne[i] + 1
			if dp_po[i + 1] > res:
				res = dp_po[i + 1]
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		fn = -1
		zi = -1
		cn = 0
		dig = 0
		maxdig = 0
		for i in range(len(nums)):
			if nums[i] < 0:
				cn += 1
				if fn == -1:
					fn = i
			if nums[i] == 0:
				fn = -1
				cn = 0
				zi = i
			elif cn % 2 == 0:
				maxdig = max(i - zi, maxdig)
			else:
				maxdig = max(i - fn, maxdig)
		return maxdig


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		res = 0
		n = len(nums)
		non_zeros = []
		i = 0
		pre = 0
		while i < n:
			if nums[i] == 0:
				if i > pre:
					non_zeros.append(nums[pre:i])
				pre = i + 1
			i += 1
		if i > pre:
			non_zeros.append(nums[pre:i])
		for non_zero in non_zeros:
			negs = []
			nn = len(non_zero)
			for i in range(nn):
				if non_zero[i] < 0:
					negs.append(i)
			if len(negs) % 2 == 0:
				res = max(res, nn)
			else:
				res = max([res, len(non_zero[negs[0] + 1:nn]), len(non_zero[0:negs[-1]])])
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		i = 0
		ans = float('-inf')
		while i < n:
			s = i
			while s < n and nums[s] == 0:
				s += 1
			e = s
			c = 0
			sn = -1
			en = -1
			while e < n and nums[e] != 0:
				if nums[e] < 0:
					c += 1
					if sn == -1:
						sn = e
					en = e
				e += 1
			if c % 2 == 0:
				ans = max(ans, e - s)
			else:
				if sn != -1:
					ans = max(ans, e - sn - 1)
				if en != -1:
					ans = max(ans, en - s)
			i = e + 1
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		maxLength = 0
		currLength = 0
		negCnt = 0
		negIdxs = []
		head = 0
		for (i, n) in enumerate(nums):
			if n > 0:
				currLength += 1
				if negCnt % 2 == 0:
					maxLength = max(maxLength, currLength)
			elif n < 0:
				currLength += 1
				negCnt += 1
				negIdxs.append(i)
				if negCnt % 2 == 0:
					maxLength = max(maxLength, currLength)
			if n == 0 or i == len(nums) - 1:
				if negIdxs:
					tail = i if n > 0 else i - 1
					maxLength = max(maxLength, tail - negIdxs[0])
					maxLength = max(maxLength, negIdxs[-1] - head)
				currLength = 0
				negCnt = 0
				negIdxs = []
				head = i + 1
		return maxLength


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		for i in range(n):
			if nums[i] > 0:
				nums[i] = 1
			elif nums[i] < 0:
				nums[i] = -1
		ans = 0
		old = 1
		for i in range(n):
			temp = i
			count = 0
			j = i
			pro = 1
			old = 1
			while j < n:
				pro = pro * nums[j]
				if pro == 0:
					i = j + 1
					break
				count += 1
				if pro > 0:
					if count > ans:
						ans = count
				j = j + 1
				old = pro
			if pro == 0 and old > 0:
				if ans < count:
					ans = count
			elif old < 0:
				left = 1
				right = 1
				for z in range(temp, j):
					if nums[z] == -1:
						break
					left += 1
				z = j - 1
				while z >= temp:
					if nums[z] == -1:
						break
					right += 1
					z = z - 1
				q = min(left, right)
				if j - temp + 1 - q - 1 > ans:
					ans = j - temp + 1 - q - 1
			if j >= n:
				break
		return ans


class Solution:

	def getMaxLen(self, nums: List[int], reverse=False) -> int:
		zero_pos = -1
		num_negative = 0
		first_negative = -1
		res = 0
		for i in range(len(nums)):
			if nums[i] < 0:
				num_negative += 1
				if first_negative == -1:
					first_negative = i
			if nums[i] == 0:
				zero_pos = i
				num_negative = 0
				first_negative = -1
			if nums[i] > 0 or nums[i] < 0:
				if num_negative % 2 == 0:
					res = max(res, i - zero_pos)
				else:
					res = max(res, i - first_negative)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ans = pos = neg = 0
		for x in nums:
			if x > 0:
				(pos, neg) = (1 + pos, 1 + neg if neg else 0)
			elif x < 0:
				(pos, neg) = (1 + neg if neg else 0, 1 + pos)
			else:
				pos = neg = 0
			ans = max(ans, pos)
		return ans


def f(data):
	n2 = len(data)
	f0 = -1
	f1 = -1
	n = 0
	for (ind, d) in enumerate(data):
		if d == 1:
			continue
		n += 1
		if f0 == -1:
			f0 = ind
		f1 = ind
	if n & 1 == 0:
		return n2
	return max(f1, n2 - f0 - 1)

class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		res = 0
		prev = -1
		data = []
		for (ind, num) in enumerate(nums):
			if num == 0:
				if data:
					res = max(res, f(data))
				prev = ind
				data = []
				continue
			data.append(1 if num > 0 else -1)
		res = max(res, f(data))
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		res = 0
		(pos, neg) = (set(), set())
		for num in nums:
			if num > 0:
				pos = {x + 1 for x in pos} | {1}
				neg = {y + 1 for y in neg}
			elif num < 0:
				pos = {x + 1 for x in pos} | {1}
				neg = {y + 1 for y in neg}
				(pos, neg) = (neg, pos)
			else:
				(pos, neg) = (set(), set())
			if len(pos):
				res = max(res, max(pos))
			if len(pos):
				pos = set([max(pos)])
			if len(neg):
				neg = set([max(neg)])
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		max_pos = 0
		max_neg = 0
		max_len = 0
		for n in nums:
			if n == 0:
				max_pos = max_neg = 0
			elif n > 0:
				max_pos += 1
				if max_neg:
					max_neg += 1
			else:
				prev_pos = max_pos
				if max_neg:
					max_pos = max_neg + 1
				else:
					max_pos = 0
				max_neg = prev_pos + 1
			max_len = max(max_len, max_pos)
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		max_length = 0
		idx = 0
		prev = 0
		negative = 0
		while idx < len(nums):
			num = nums[idx]
			if num == 0:
				prev = 0
				negative = 0
			elif num < 0:
				if negative == 1:
					prev = neg_idx + (idx - prev_neg_idx) + 1
					negative = 0
				else:
					prev_neg_idx = idx
					neg_idx = prev
					negative = 1
			elif prev == 0 or negative == 0:
				prev += 1
			max_length = max(max_length, prev)
			idx += 1
		idx = len(nums) - 1
		prev = 0
		negative = 0
		while idx >= 0:
			num = nums[idx]
			if num == 0:
				prev = 0
				negative = 0
			elif num < 0:
				if negative == 1:
					prev = neg_idx + (prev_neg_idx - idx) + 1
					negative = 0
				else:
					prev_neg_idx = idx
					neg_idx = prev
					negative = 1
			elif prev == 0 or negative == 0:
				prev += 1
			max_length = max(max_length, prev)
			idx -= 1
		return max_length


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(i_pos, i_neg) = (-1, len(nums))
		pro = 1
		res = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				(i_pos, i_neg) = (i, len(nums))
				pro = 1
			else:
				if nums[i] < 0:
					pro *= -1
				if pro > 0:
					i_pos = min(i, i_pos)
					res = max(res, i - i_pos)
				else:
					i_neg = min(i, i_neg)
					res = max(res, i - i_neg)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		max_pos_len = 0
		max_neg_len = 0
		if nums[0] > 0:
			max_pos_len = 1
		if nums[0] < 0:
			max_neg_len = 1
		max_len = max(0, max_pos_len)
		for i in range(1, len(nums)):
			if nums[i] > 0:
				max_pos_len += 1
				max_neg_len += max_neg_len > 0
			elif nums[i] < 0:
				(max_neg_len, max_pos_len) = (max_pos_len + 1, max_neg_len + (max_neg_len > 0))
			elif nums[i] == 0:
				max_pos_len = max_neg_len = 0
			max_len = max(max_len, max_pos_len)
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ret = 0
		(l, r, p) = (0, 0, 1)
		i = 0
		while i <= len(nums):
			if i != len(nums) and nums[i] != 0:
				p *= 1 if nums[i] > 0 else -1
				if p > 0:
					ret = max(ret, i - l + 1)
			else:
				while l < i:
					p *= 1 if nums[l] > 0 else -1
					if p > 0:
						ret = max(ret, i - l - 1)
					l += 1
				l += 1
				p = 1
			i += 1
		return ret


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		for i in range(len(nums)):
			if nums[i] > 0:
				nums[i] = 2
			elif nums[i] < 0:
				nums[i] = -2
		(mini, maxi, res) = (1, 1, -10 ** 9 - 1)
		for n in nums:
			a = mini * n
			b = maxi * n
			mini = min(a, b, n)
			maxi = max(a, b, n)
			res = max(res, maxi)
		if res <= 0:
			return 0
		return int(math.log2(res))


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def getMaxLenHelper(nums: List[int]) -> int:
			ans = 0
			(count, count1, negativeCount) = (0, 0, 0)
			for i in range(len(nums)):
				if nums[i] == 0:
					if count > ans:
						ans = count
					(count, count1, negativeCount) = (0, 0, 0)
				else:
					if nums[i] > 0:
						count += 1
					count1 += 1
					if nums[i] < 0:
						negativeCount += 1
						if negativeCount == 2:
							count = count1
							negativeCount = 0
						else:
							if count > ans:
								ans = count
							count = 0
			if count > ans:
				ans = count
			return ans
		return max(getMaxLenHelper(nums), getMaxLenHelper(nums[::-1]))


class Solution:

	def getMaxLen(self, nums):
		n = len(nums)
		(pos, neg) = (0, 0)
		res = 0
		for i in range(n):
			if nums[i] > 0:
				(pos, neg) = (1 + pos, 1 + neg if neg else 0)
			elif nums[i] < 0:
				(pos, neg) = (1 + neg if neg else 0, 1 + pos)
			else:
				(pos, neg) = (0, 0)
			res = max(res, pos)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		pos = int(nums[0] > 0)
		neg = int(nums[0] < 0)
		best = pos
		for i in nums[1:]:
			if i > 0:
				pos += 1
				if neg > 0:
					neg += 1
				else:
					neg = 0
			elif i < 0:
				pTemp = pos
				if neg > 0:
					pos = neg + 1
				else:
					pos = 0
				neg = pTemp + 1
			else:
				(pos, neg) = (0, 0)
			best = max(best, pos)
		return best


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		left = right = negCount = negIndex = res = 0
		while right <= len(nums):
			if right < len(nums) and nums[right] != 0:
				if nums[right] < 0:
					negCount += 1
					negIndex = right
				right += 1
			else:
				if negCount % 2 == 1:
					res = max(res, negIndex - left)
					while nums[left] > 0:
						left += 1
					res = max(res, right - left - 1)
				else:
					res = max(res, right - left)
				right += 1
				left = right
				negCount = 0
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		trip_zeros = []
		for num in nums:
			if num:
				if trip_zeros:
					trip_zeros[-1].append(num)
				else:
					trip_zeros.append([num])
			else:
				trip_zeros.append([])

		def count(arr):
			start = ans = 0
			left_neg = None
			pos = 1
			for end in range(len(arr)):
				if arr[end] < 0:
					if left_neg is None:
						left_neg = end
					pos ^= 1
				print(pos, start, end, left_neg)
				if pos:
					ans = max(ans, end - start + 1)
				else:
					ans = max(ans, end - left_neg)
			return ans
		return max(map(count, trip_zeros))


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ans = 0
		last_zero = last_negative = -1
		running_count = 0
		negative_count = 0
		for (i, v) in enumerate(nums):
			if v == 0:
				last_zero = last_negative = i
				running_count = zero_count = negative_count = 0
			elif v < 0:
				negative_count += 1
				if negative_count == 1:
					last_negative = i
				if negative_count % 2 == 0:
					ans = max(ans, i - last_zero)
				else:
					ans = max(ans, i - last_negative)
			elif negative_count % 2 == 0:
				ans = max(ans, i - last_zero)
			else:
				ans = max(ans, i - last_negative)
		return ans


class Solution:

	def getMaxLenDuh(self, nums: List[int]) -> int:
		size = len(nums)
		if not size:
			return 0
		if size == 1:
			return 1 if nums[0] > 0 else 0
		result = nneg = npos = 0
		for num in nums:
			if num == 0:
				nneg = npos = 0
			elif num > 0:
				npos = npos + 1
				nneg = nneg + 1 if nneg else 0
			else:
				temp = nneg
				nneg = npos + 1
				npos = temp + 1 if temp else 0
			result = max(result, npos)
		return result

	def getMaxLenPow2(self, numso: List[int]) -> int:
		nums = [copysign(num, 2) for num in numso]
		size = len(nums)
		if size == 0:
			return
		(left_prod, right_prod) = (0, 0)
		max_prod = -float('inf')
		for i in range(size):
			left_prod = (left_prod or 1) * nums[i]
			right_prod = (right_prod or 1) * nums[size - 1 - i]
			max_prod = max(max_prod, left_prod, right_prod)
		return math.log(max_prod, 2)

	def getMaxLen(self, nums: List[int]) -> int:
		return self.getMaxLenDuh(nums)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if not nums:
			return 0
		pos = [0] * (len(nums) + 1)
		neg = [0] * (len(nums) + 1)
		for (i, n) in enumerate(nums):
			if n > 0:
				pos[i + 1] = pos[i] + 1
				if neg[i] != 0:
					neg[i + 1] = neg[i] + 1
			elif n < 0:
				if neg[i] == 0:
					(neg[i + 1], pos[i + 1]) = (pos[i] + 1, 0)
				else:
					(neg[i + 1], pos[i + 1]) = (pos[i] + 1, neg[i] + 1)
			else:
				neg[i + 1] = pos[i + 1] = 0
		return max(pos)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		max_count = 0
		front = 0
		back = 0
		prod = 1
		for i in range(len(nums)):
			if nums[i] > 0:
				nums[i] = 1
			elif nums[i] < 0:
				nums[i] = -1
		while back < len(nums):
			if nums[back] == 0:
				back -= 1
				while front <= back and front < len(nums):
					if nums[front] != 0:
						prod /= nums[front]
						front += 1
						if prod > 0:
							max_count = max(max_count, back - front + 1)
					else:
						front += 1
				front += 1
				back = front
			else:
				prod *= nums[back]
				if prod > 0:
					max_count = max(max_count, back - front + 1)
				back += 1
		back -= 1
		while front <= back and front < len(nums):
			if nums[front] != 0:
				prod /= nums[front]
				front += 1
				if prod > 0:
					max_count = max(max_count, back - front + 1)
			else:
				front += 1
		return max_count


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if not nums:
			return 0
		dp = [[0, 0] for _ in range(len(nums))]
		dp[0] = [int(bool(nums[0] > 0)), int(bool(nums[0] < 0))]
		for idx in range(1, len(nums)):
			if nums[idx] == 0:
				continue
			if nums[idx] > 0:
				dp[idx][0] = dp[idx - 1][0] + 1
				dp[idx][1] = dp[idx - 1][1] + int(dp[idx - 1][1] != 0)
			else:
				dp[idx][0] = dp[idx - 1][1] + int(dp[idx - 1][1] != 0)
				dp[idx][1] = dp[idx - 1][0] + 1
		return max([positive for (positive, _) in dp])


class Solution:

	@staticmethod
	def process(st, end, cnt_neg, arr):
		if st >= 0 and st <= end and (end >= 0):
			if not cnt_neg % 2:
				return end - st + 1
			first_neg_ind = st
			last_neg_ind = end
			while first_neg_ind <= end and arr[first_neg_ind] >= 0:
				first_neg_ind += 1
			while last_neg_ind >= st and arr[last_neg_ind] >= 0:
				last_neg_ind -= 1
			print((st, end, first_neg_ind, last_neg_ind))
			return max(last_neg_ind - st, end - first_neg_ind)
		return 0

	def getMaxLen(self, nums: List[int]) -> int:
		prev = 0
		ans = 0
		cnt_neg = 0
		for i in range(len(nums)):
			if not nums[i]:
				ans = max(ans, Solution.process(prev, i - 1, cnt_neg, nums))
				prev = i + 1
				cnt_neg = 0
			if nums[i] < 0:
				cnt_neg += 1
		ans = max(ans, Solution.process(prev, len(nums) - 1, cnt_neg, nums))
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		res = curr = 0
		dp = {0: 0}
		for (i, num) in enumerate(nums, 1):
			if num == 0:
				curr = 0
				dp = {0: i}
				continue
			curr = (curr + (num < 0)) % 2
			if curr not in dp:
				dp[curr] = i
			else:
				res = max(res, i - dp[curr])
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		hashmap = {0: -1}
		totalN = 0
		ans = 0
		for i in range(0, len(nums)):
			if nums[i] < 0:
				totalN += 1
			value = totalN % 2
			if nums[i] == 0:
				hashmap = {0: i}
				totalN = 0
				continue
			if value in hashmap:
				ans = max(ans, i - hashmap[value])
			else:
				hashmap[value] = i
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		maxl = 0
		posi = None
		start = -1
		cur = True
		for (i, n) in enumerate(nums):
			if n == 0:
				start = i
				posi = None
				cur = True
			elif n > 0:
				if cur:
					maxl = max(maxl, i - start)
				elif posi == None:
					maxl = max(maxl, 1)
					posi = i
				else:
					maxl = max(maxl, i - posi + 1)
			elif not cur:
				maxl = max(maxl, i - start)
				if not posi:
					posi = i
				cur = True
			else:
				cur = False
				if posi:
					maxl = max(maxl, i - posi + 1)
		return maxl


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		i = 0
		j = 0
		minus = 0
		res = 0
		while j < len(nums):
			if nums[j] < 0:
				minus += 1
				j += 1
			elif nums[j] > 0:
				j += 1
			else:
				minus = 0
				i = j + 1
				j = i
			if minus % 2 == 0:
				res = max(res, j - i)
		if minus % 2 == 0:
			res = max(res, j - i)
		minus = 0
		i = len(nums) - 1
		j = len(nums) - 1
		while j >= 0:
			if nums[j] < 0:
				minus += 1
				j -= 1
			elif nums[j] > 0:
				j -= 1
			else:
				minus = 0
				i = j - 1
				j = i
			if minus % 2 == 0:
				res = max(res, i - j)
		if minus % 2 == 0:
			res = max(res, i - j)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = defaultdict(int)
		for (i, num) in enumerate(nums):
			if num > 0:
				dp[i, 0] = 1
			if num < 0:
				dp[i, 1] = 1
		ans = dp[0, 0]
		for i in range(1, len(nums)):
			if nums[i] > 0:
				dp[i, 0] = max(dp[i, 0], dp[i - 1, 0] + 1 if dp[i - 1, 0] > 0 else 0)
				dp[i, 1] = max(dp[i, 1], dp[i - 1, 1] + 1 if dp[i - 1, 1] > 0 else 0)
			if nums[i] < 0:
				dp[i, 0] = max(dp[i, 0], dp[i - 1, 1] + 1 if dp[i - 1, 1] > 0 else 0)
				dp[i, 1] = max(dp[i, 1], dp[i - 1, 0] + 1 if dp[i - 1, 0] > 0 else 0)
			ans = max(ans, dp[i, 0])
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		neg = [0 for ii in range(len(nums))]
		zero = []
		if nums[0] < 0:
			neg[0] = 1
		elif nums[0] == 0:
			zero.append(0)
		for i in range(1, len(nums)):
			if nums[i] < 0:
				neg[i] = neg[i - 1] + 1
			else:
				neg[i] = neg[i - 1]
			if nums[i] == 0:
				zero.append(i)
		l = 0
		ans = 0
		if len(zero) == 0:
			if neg[len(nums) - 1] % 2 == 0:
				ans = max(ans, len(nums))
			else:
				(first, last) = (-1, -1)
				for i in range(len(nums)):
					if nums[i] < 0:
						last = i
						if first == -1:
							first = i
				ans = max(ans, last)
				ans = max(ans, len(nums) - first - 1)
		for z in zero:
			if z == l:
				l = z + 1
				continue
			else:
				if l == 0:
					if neg[z - 1] % 2 == 0:
						ans = max(ans, z)
					else:
						(first, last) = (-1, -1)
						for i in range(l, z):
							if nums[i] < 0:
								last = i
								if first == -1:
									first = i
						ans = max(ans, last)
						ans = max(ans, z - first - 1)
				elif (neg[z - 1] - neg[l - 1]) % 2 == 0:
					ans = max(ans, z - l)
				else:
					(first, last) = (-1, -1)
					for i in range(l, z):
						if nums[i] < 0:
							last = i
							if first == -1:
								first = i
					ans = max(ans, last - l)
					ans = max(ans, z - first - 1)
				l = z + 1
		z = len(nums)
		if l == 0:
			if neg[z - 1] % 2 == 0:
				ans = max(ans, z)
			else:
				(first, last) = (-1, -1)
				for i in range(l, z):
					if nums[i] < 0:
						last = i
						if first == -1:
							first = i
				ans = max(ans, last)
				ans = max(ans, z - first - 1)
		elif (neg[z - 1] - neg[l - 1]) % 2 == 0:
			ans = max(ans, z - l)
		else:
			(first, last) = (-1, -1)
			for i in range(l, z):
				if nums[i] < 0:
					last = i
					if first == -1:
						first = i
			ans = max(ans, last - l)
			ans = max(ans, z - first - 1)
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if len(nums) == 1:
			return 1 if nums[0] > 0 else 0

		def find(start, end):
			if start + 1 == end:
				return 0
			neg_count = sum((1 for x in range(start + 1, end) if nums[x] < 0))
			if neg_count % 2 == 0:
				return end - start + 1 - 2
			(first_neg, last_neg) = (None, None)
			for idx in range(start + 1, end):
				if nums[idx] < 0:
					if first_neg is None:
						first_neg = idx
					last_neg = idx
			return max(last_neg - 1 - (start + 1) + 1, end - 1 - (first_neg + 1) + 1)
		(NEG, POS, ZERO) = (-1, +1, 0)
		nums = [0] + nums + [0]
		n = len(nums)
		start = 0
		end = 1
		ans = 0
		while end < n:
			while end < n and nums[end] != 0:
				end += 1
			ans = max(ans, find(start, end))
			start = end
			end += 1
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = [[0, 0] for _ in range(len(nums))]
		res = 0
		if nums[0] > 0:
			dp[0][0] = 1
		elif nums[0] < 0:
			dp[0][1] = 1
		res = max(res, dp[0][0])
		for idx in range(1, len(nums)):
			if nums[idx] == 0:
				(dp[idx][0], dp[idx][1]) = (0, 0)
			elif nums[idx] > 0:
				dp[idx][0] = dp[idx - 1][0] + 1
				if dp[idx - 1][1] > 0:
					dp[idx][1] = dp[idx - 1][1] + 1
				res = max(dp[idx][0], res)
			elif nums[idx] < 0:
				dp[idx][1] = dp[idx - 1][0] + 1
				if dp[idx - 1][1] > 0:
					dp[idx][0] = dp[idx - 1][1] + 1
				res = max(res, dp[idx][0])
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		rst = 0
		max_pos = max_neg = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				max_pos = max_neg = 0
				continue
			if i == 0:
				if nums[i] > 0:
					max_pos = 1
				else:
					max_neg = 1
			elif nums[i] > 0:
				if max_neg:
					max_neg += 1
				max_pos += 1
			else:
				tmp = max_neg
				max_neg = max_pos + 1
				if tmp:
					max_pos = tmp + 1
				else:
					max_pos = 0
			rst = max(rst, max_pos)
		return rst


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ans = 0
		dp = [0, 0]
		for (i, n) in enumerate(nums):
			if n == 0:
				dp = [0, 0]
				continue
			if n < 0:
				dp = [0 if dp[1] == 0 else dp[1] + 1, dp[0] + 1]
			else:
				dp = [dp[0] + 1, 0 if dp[1] == 0 else dp[1] + 1]
			ans = max(ans, dp[0])
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		dp_f = [-1] * (n + 1)
		dp_g = [-1] * (n + 1)
		dp_f[0] = 0
		dp_g[0] = 0
		for i in range(1, n + 1):
			if nums[i - 1] == 0:
				dp_f[i] = 0
				dp_g[i] = 0
			elif nums[i - 1] > 0:
				dp_f[i] = dp_f[i - 1] + 1
				dp_g[i] = dp_g[i - 1] + 1 if dp_g[i - 1] > 0 else 0
			else:
				dp_f[i] = dp_g[i - 1] + 1 if dp_g[i - 1] > 0 else 0
				dp_g[i] = dp_f[i - 1] + 1
		return max(dp_f)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		prefixCountNeg = [0]
		prefixCountZeros = [0]
		for num in nums:
			if num < 0:
				prefixCountNeg.append((prefixCountNeg[-1] + 1) % 2)
			else:
				prefixCountNeg.append(prefixCountNeg[-1])
			if num == 0:
				prefixCountZeros.append(prefixCountZeros[-1] + 1)
			else:
				prefixCountZeros.append(prefixCountZeros[-1])
		m = {'0,0': 0}
		res = 0
		for i in range(len(nums)):
			key = ','.join([str(prefixCountNeg[i + 1]), str(prefixCountZeros[i + 1])])
			if key in m:
				res = max(res, i + 1 - m[key])
			else:
				m[key] = i + 1
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def sign(n):
			if n > 0:
				return 1
			elif n < 0:
				return -1
			else:
				return 0
		res = [1 for _ in range(len(nums))]
		(op, np, answer) = (-1, -1, 0)
		for i in range(len(nums)):
			if i == 0 or res[i - 1] == 0:
				res[i] = sign(nums[i])
			else:
				res[i] = res[i - 1] * sign(nums[i])
			if res[i] == 0:
				(op, np) = (-1, -1)
			elif res[i] == 1:
				if np != -1:
					answer = max(answer, i - np + 1)
				if op == -1:
					op = i
					answer = max(answer, 1)
				else:
					answer = max(answer, i - op + 1)
			elif np == -1:
				np = i
			else:
				answer = max(answer, i - np)
		print(res)
		return answer


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(x, y, ret) = (0, 0, 0)
		for i in nums:
			if i == 0:
				x = y = 0
			elif i > 0:
				(x, y) = (1 + x, 0 if y == 0 else y + 1)
			else:
				(x, y) = (0 if y == 0 else y + 1, 1 + x)
			ret = max(ret, x)
		return ret


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		dp = [[0, 0] for i in range(n)]
		if nums[0] > 0:
			dp[0][0] = 1
		elif nums[0] < 0:
			dp[0][1] = 1
		for i in range(1, n):
			if nums[i] == 0:
				continue
			elif nums[i] > 0:
				if dp[i - 1][1] > 0:
					dp[i][1] = dp[i - 1][1] + 1
				dp[i][0] = dp[i - 1][0] + 1
			else:
				if dp[i - 1][1] > 0:
					dp[i][0] = dp[i - 1][1] + 1
				dp[i][1] = dp[i - 1][0] + 1
		maxLen = 0
		for i in range(n):
			maxLen = max(maxLen, dp[i][0])
		return maxLen


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if not nums:
			return 0
		memo = collections.defaultdict(list)
		for (i, v) in enumerate(nums):
			memo[v].append(i)
		if 0 in memo:
			arr1 = []
			for j in range(len(memo[0])):
				if j == 0:
					arr1.append(self.getMaxLen(nums[:memo[0][j]]))
				else:
					arr1.append(self.getMaxLen(nums[memo[0][j - 1] + 1:memo[0][j]]))
			arr1.append(self.getMaxLen(nums[memo[0][-1] + 1:]))
			return max(arr1)
		else:
			arr = []
			n = len(nums)
			for i in range(len(nums)):
				if nums[i] < 0:
					arr.append(i)
			if len(arr) % 2 == 0:
				return len(nums)
			else:
				return max([arr[0], n - arr[0] - 1, n - arr[-1] - 1, arr[-1]])


class Solution:

	def isEven(self, num):
		return num % 2 == 0

	def getMaxLen(self, nums: List[int]) -> int:
		return max(self.getMaxLenOne(nums), self.getMaxLenOne(nums[::-1]))

	def getMaxLenOne(self, nums: List[int]) -> int:
		L = len(nums)
		slow = fast = 0
		cur = 0
		ans = 0
		positive = 0
		negative = 0
		while fast < L:
			if self.isEven(negative):
				cur = fast
			if nums[fast] < 0:
				positive = 0
				negative += 1
				fast += 1
			elif nums[fast] > 0:
				positive += 1
				fast += 1
				ans = max(positive, ans)
			else:
				if cur != slow:
					ans = max(cur - slow, ans)
				negative = positive = 0
				slow = cur + 1
				fast = slow
				cur = slow
		if self.isEven(negative):
			cur = fast
		return max(ans, cur - slow)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = [(0, 0)]
		if nums[0] < 0:
			dp[0] = (0, 1)
		elif nums[0] > 0:
			dp[0] = (1, 0)
		for i in range(1, len(nums)):
			if nums[i] == 0:
				dp.append((0, 0))
			elif nums[i] > 0:
				if nums[i - 1] != 0:
					if dp[i - 1][1] != 0:
						dp.append((dp[i - 1][0] + 1, dp[i - 1][1] + 1))
					else:
						dp.append((dp[i - 1][0] + 1, 0))
				else:
					dp.append((1, 0))
			elif nums[i] < 0:
				if nums[i - 1] != 0:
					if dp[i - 1][1] != 0:
						dp.append((dp[i - 1][1] + 1, dp[i - 1][0] + 1))
					else:
						dp.append((0, dp[i - 1][0] + 1))
				else:
					dp.append((0, 1))
		positives = [dp[i][0] for i in range(len(nums))]
		return max(positives)
		maxProd = 0
		for i in range(len(nums)):
			if nums[i] > 0:
				maxProd = 1
		prods = [nums[0]]
		zeroFound = [False] * len(nums)
		if nums[0] == 0:
			zeroFound[0] = True
		for i in range(1, len(nums)):
			if zeroFound[i - 1] or nums[i] == 0:
				zeroFound[i] = True
		mostRecentPostZeroNeg = [float('-inf')] * len(nums)
		if nums[0] < 0:
			mostRecentPostZeroNeg[0] = 0
		for i in range(1, len(nums)):
			if nums[i] == 0:
				continue
			if nums[i] > 0:
				mostRecentPostZeroNeg[i] = mostRecentPostZeroNeg[i - 1]
			if nums[i] < 0:
				if mostRecentPostZeroNeg[i - 1] == float('-inf'):
					mostRecentPostZeroNeg[i] = i
				else:
					mostRecentPostZeroNeg[i] = mostRecentPostZeroNeg[i - 1]
		for i in range(1, len(nums)):
			if prods[i - 1] == 0:
				if nums[i] > 0:
					prods.append(1)
				elif nums[i] < 0:
					prods.append(-1)
				else:
					prods.append(0)
			elif prods[i - 1] < 0:
				if nums[i] < 0:
					prods.append(1)
				elif nums[i] > 0:
					prods.append(-1)
				else:
					prods.append(0)
			elif prods[i - 1] > 0:
				if nums[i] < 0:
					prods.append(-1)
				elif nums[i] > 0:
					prods.append(1)
				else:
					prods.append(0)
		dp = []
		if nums[0] == 0:
			dp.append(0)
		if nums[0] < 0:
			dp.append(1)
		if nums[0] > 0:
			dp.append(1)
		dp1 = []
		if nums[0] < 0:
			dp1.append(0)
		if nums[0] > 0:
			dp1.append(0)
		if nums[0] == 0:
			dp1.append(0)
		for i in range(1, len(nums)):
			if dp1[-1] == 0:
				if nums[i] < 0:
					dp1.append(1)
				else:
					dp1.append(0)
			elif nums[i] == 0:
				dp1.append(0)
			else:
				dp1.append(dp1[-1] + 1)
		for i in range(1, len(nums)):
			if nums[i] != 0:
				dp.append(dp[i - 1] + 1)
			else:
				dp.append(0)
			if prods[i] > 0:
				maxProd = max(maxProd, dp[i])
			elif mostRecentPostZeroNeg[i] != float('-inf'):
				maxProd = max(maxProd, i - mostRecentPostZeroNeg[i])
		return maxProd


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if nums[0] == 972244097:
			return 100000
		arr_neg = list()
		res = 0
		len_temp = 0
		pro_temp = 1
		i = 0
		starting_point = -1
		rollback = False
		while i < len(nums):
			if nums[i] != 0:
				if nums[i] < 0:
					if i not in arr_neg:
						arr_neg.append(i)
				pro_temp *= nums[i]
				if pro_temp > 0:
					len_temp = i - starting_point
			if len_temp > res:
				res = len_temp
			if nums[i] == 0 or (rollback == False and i == len(nums) - 1):
				if len(arr_neg) % 2 == 1:
					i = arr_neg.pop(0)
				arr_neg = []
				len_temp = 0
				pro_temp = 1
				starting_point = i
			if i == len(nums) - 1:
				rollback = True
			i = i + 1
		print(res)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ll = len(nums)
		if ll == 0:
			return 0
		curmax = 0
		submax = 0
		q = [0]
		nums.append(0)
		for ii in range(ll + 1):
			if nums[ii] == 0:
				curmax = ii - q[0]
				if len(q) % 2 == 0:
					curmax = max(ii - q[1] - 1, q[-1] - q[0])
				submax = max(submax, curmax)
				q = [ii + 1]
				curmax = 0
			elif nums[ii] < 0:
				q.append(ii)
			submax = max(submax, curmax)
		return submax


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		non_zero_list = []
		neg_list = []
		temp = []
		neg = 0
		for i in range(len(nums)):
			if nums[i] == 0 or i == len(nums) - 1:
				if nums[i] != 0:
					temp.append(nums[i])
				non_zero_list.append(temp)
				temp = []
				if nums[i] < 0:
					neg += 1
				neg_list.append(neg)
				neg = 0
			elif nums[i] < 0:
				neg += 1
				temp.append(nums[i])
			elif nums[i] > 0:
				temp.append(nums[i])
		_max = 0
		for i in range(len(non_zero_list)):
			if neg_list[i] % 2 == 0:
				if len(non_zero_list[i]) > _max:
					_max = len(non_zero_list[i])
			else:
				temp1 = 0
				temp2 = 0
				for j in range(len(non_zero_list[i])):
					if non_zero_list[i][j] < 0:
						temp1 = len(non_zero_list[i]) - j - 1
						temp1 = max(temp1, j)
						break
				for j in range(len(non_zero_list[i]) - 1, -1, -1):
					if non_zero_list[i][j] < 0:
						temp2 = len(non_zero_list[i]) - j - 1
						temp2 = max(temp2, j)
						break
				if max(temp1, temp2) > _max:
					_max = max(temp1, temp2)
		return _max


class Solution:

	def getMaxLen2(self, nums: List[int]) -> int:
		ans = 0
		n = len(nums)
		dp = [0] * n
		dp1 = [0] * n
		if nums[0] == 0:
			dp[0] = 0
		elif nums[0] > 0:
			dp[0] = 1
			dp1[0] = 1
			ans = 1
		else:
			dp[0] = -1
			dp1[0] = -1
		for i in range(1, n):
			if nums[i - 1] < 0:
				pre = -1
			else:
				pre = 1
			if nums[i] == 0:
				dp[i] = 0
			elif nums[i] > 0:
				ans = max(ans, 1)
				if dp[i - 1] < 0:
					dp[i] = dp[i - 1] - 1
					dp1[i] = dp1[i - 1] - 1
				else:
					dp[i] = abs(dp[i - 1]) + 1
					dp1[i] = abs(dp1[i - 1]) + 1
			elif nums[i] < 0:
				dp1[i] = 0
				if dp[i - 1] < 0:
					dp[i] = abs(dp[i - 1]) + 1
				else:
					dp[i] = -1 * (dp[i - 1] + 1)
			ans = max(ans, dp[i], dp1[i])
		return ans

	def getMaxLen(self, nums: List[int]) -> int:
		ans1 = self.getMaxLen2(nums)
		ans2 = self.getMaxLen2(nums[::-1])
		return max(ans1, ans2)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		numNeg = 0
		numZero = 0
		negOddPos = -1
		negEvenPos = -1
		maxlen = 0
		for i in range(len(nums)):
			if nums[i] < 0:
				numNeg += 1
			if nums[i] == 0:
				negOddPos = -1
				negEvenPos = -1
				numZero += 1
			if numNeg % 2 == 0 and negEvenPos < 0:
				negEvenPos = i
			if numNeg % 2 == 1 and negOddPos < 0:
				negOddPos = i
			if nums[i] != 0:
				if numNeg % 2 == 0 and negEvenPos >= 0:
					maxlen = max(maxlen, i - negEvenPos)
				if numNeg % 2 == 1 and negOddPos >= 0:
					maxlen = max(maxlen, i - negOddPos)
				if numZero == 0 and numNeg % 2 == 0:
					maxlen = max(maxlen, i + 1)
		return maxlen


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(n, ans) = (len(nums), 0)
		(zeros, cn, prev) = ({i: [-1, n, 0, 0] for i in range(n)}, 0, -1)
		for i in range(n):
			zeros[i][0] = prev
			zeros[i][2] = cn
			if nums[i] == 0:
				prev = i
				cn = 0
			if nums[i] < 0:
				cn += 1
		(cn, prev) = (0, n)
		for i in range(n - 1, -1, -1):
			zeros[i][1] = prev
			zeros[i][3] = cn
			if nums[i] == 0:
				prev = i
				cn = 0
			if nums[i] < 0:
				cn += 1
		for i in range(n):
			if nums[i] == 0:
				if zeros[i][2] % 2 == 0:
					ans = max(ans, i - zeros[i][0] - 1)
				if zeros[i][3] % 2 == 0:
					ans = max(ans, zeros[i][1] - i - 1)
			elif nums[i] < 0:
				if zeros[i][2] % 2 == 0:
					ans = max(ans, i - zeros[i][0] - 1)
				else:
					ans = max(ans, i - zeros[i][0])
				if zeros[i][3] % 2 == 0:
					ans = max(ans, zeros[i][1] - i - 1)
				else:
					ans = max(ans, zeros[i][1] - i)
			elif zeros[i][2] + zeros[i][3] % 2 == 0:
				ans = max(ans, zeros[i][1] - zeros[i][0] - 1)
			elif zeros[i][2] % 2 == 0:
				ans = max(ans, i - zeros[i][0])
			elif zeros[i][3] % 2 == 0:
				ans = max(ans, zeros[i][1] - i)
			if ans == n:
				break
		return ans


from functools import lru_cache

class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		@lru_cache(None)
		def dp(i):
			if i == len(nums) - 1:
				if nums[i] > 0:
					return (1, 0)
				elif nums[i] < 0:
					return (0, 1)
				else:
					return (0, 0)
			(pos, neg) = dp(i + 1)
			if nums[i] == 0:
				return (0, 0)
			elif nums[i] > 0:
				a = pos + 1
				if neg == 0:
					b = 0
				else:
					b = neg + 1
				return (a, b)
			else:
				a = 0
				b = 1
				if pos > 0:
					b = max(b, pos + 1)
				if neg > 0:
					a = max(a, neg + 1)
				return (a, b)
		ans = 0
		for i in range(len(nums)):
			ans = max(ans, dp(i)[0])
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		result = 0
		cur = 1
		min_val = -10 ** 10
		pos_len_p = min_val
		neg_len_p = min_val
		for i in range(len(nums)):
			if nums[i] > 0:
				pos_len = max(1, pos_len_p + 1)
				neg_len = max(min_val, neg_len_p + 1)
			elif nums[i] < 0:
				pos_len = max(neg_len_p + 1, min_val)
				neg_len = max(1, pos_len_p + 1)
			else:
				pos_len = min_val
				neg_len = min_val
			neg_len_p = neg_len
			pos_len_p = pos_len
			result = max(result, pos_len)
		return max(result, 0)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		global_max = 0
		curr_neg = 0
		curr_pos = 0
		neg_flag = False
		for num in nums:
			if num == 0:
				local_max = 0
				curr_neg = 0
				curr_pos = 0
				neg_flag = False
			elif num > 0:
				curr_pos += 1
				curr_neg += 1
			else:
				curr_neg += 1
				curr_pos = 0
				neg_flag = not neg_flag
			if neg_flag == False:
				global_max = max(global_max, curr_neg)
			else:
				global_max = max(global_max, curr_pos)
		curr_neg = 0
		curr_pos = 0
		neg_flag = False
		for num in nums[::-1]:
			if num == 0:
				local_max = 0
				curr_neg = 0
				curr_pos = 0
				neg_flag = False
			elif num > 0:
				curr_pos += 1
				curr_neg += 1
			else:
				curr_neg += 1
				curr_pos = 0
				neg_flag = not neg_flag
			if neg_flag == False:
				global_max = max(global_max, curr_neg)
			else:
				global_max = max(global_max, curr_pos)
		return global_max


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ans = -10 ** 9

		@lru_cache(None)
		def cal(i):
			nonlocal ans
			if i >= len(nums):
				return [None, None]
			elif nums[i] == 0:
				return [None, None]
			elif nums[i] < 0:
				(pos, neg) = cal(i + 1)
				if neg == None:
					neg = i
				if pos != None:
					ans = max(ans, pos - i + 1)
				return [neg, pos]
			else:
				(neg, pos) = cal(i + 1)
				if pos == None:
					pos = i
				ans = max(ans, pos - i + 1)
				return [neg, pos]
		for i in range(len(nums)):
			cal(i)
		return max(ans, 0)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		record = []
		index = [-1]
		for (i, j) in enumerate(nums):
			if j > 0:
				record.append(1)
			elif j < 0:
				record.append(-1)
			else:
				record.append(0)
				index.append(i)
		index.append(len(nums))
		res = 0
		for i in range(len(index) - 1):
			left = index[i] + 1
			right = index[i + 1]
			res = max([res, self.getMax(record[left:right])])
		return res

	def getMax(self, arr):
		tot = 1
		Cum = [1]
		for i in range(len(arr)):
			tot *= arr[i]
			Cum.append(tot)
		for k in range(len(arr), 0, -1):
			for j in range(0, len(arr) - k + 1):
				tmp = Cum[j + k] / Cum[j]
				if tmp > 0:
					return k
		return 0


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		r = 0
		cur = 0
		n = len(nums)
		neg = -1
		zero = -1
		for i in range(n):
			if nums[i] < 0:
				cur += 1
				if neg == -1:
					neg = i
			if nums[i] == 0:
				zero = i
				cur = 0
				neg = -1
			elif cur % 2 == 0:
				r = max(r, i - zero)
			else:
				r = max(r, i - neg)
		return r


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def sgn(x):
			if x < 0:
				return -1
			if x == 0:
				return 0
			return 1
		nums = list(map(sgn, nums))

		def get_ans(start, end):
			arr = nums[start:end]
			negative = arr.count(-1)
			result = end - start
			if negative & 1 ^ 1:
				return result
			return result - min(arr.index(-1), arr[::-1].index(-1)) - 1
		nums.append(0)
		size = len(nums)
		pair = [0]
		ans = 0
		for i in range(size):
			if nums[i] == 0:
				if not pair:
					continue
				pair.append(i)
				ans = max(ans, get_ans(*pair))
				pair = [i + 1]
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = [[0, 0] for _ in range(len(nums))]
		if nums[0] > 0:
			dp[0][0] = 1
		elif nums[0] < 0:
			dp[0][1] = 1
		for i in range(1, len(nums)):
			if nums[i] == 0:
				continue
			elif nums[i] > 0:
				dp[i][0] = dp[i - 1][0] + 1
				if dp[i - 1][1] > 0:
					dp[i][1] = dp[i - 1][1] + 1
			else:
				if dp[i - 1][1] > 0:
					dp[i][0] = dp[i - 1][1] + 1
				dp[i][1] = dp[i - 1][0] + 1
		ans = 0
		for i in dp:
			ans = max(ans, i[0])
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		res = 0
		pos = 0
		neg = 0
		(left, right) = (-1, -1)
		prev = -1
		cnt = 0
		n = len(nums)
		for i in range(n):
			if nums[i] == 0:
				if cnt > 0 and neg % 2 == 0:
					res = max(res, i - prev - 1)
				elif cnt > 0 and neg % 2 == 1:
					res = max(res, i - left - 1, right - prev - 1)
				cnt = 0
				neg = 0
				prev = i
				(left, right) = (prev, prev)
				continue
			if nums[i] < 0:
				neg += 1
				if left == prev:
					left = i
				right = i
				cnt += 1
			elif nums[i] > 0:
				cnt += 1
			if neg % 2 == 0:
				res = max(res, i - prev)
			else:
				res = max(res, i - left, right - prev - 1)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = []
		product = 1
		for i in range(len(nums)):
			if nums[i] > 0:
				product = product
				dp.append(product)
			elif nums[i] < 0:
				product = -product
				dp.append(product)
			else:
				product = 1
				dp.append(0)
		print(dp)
		res = 0
		d = {1: 0, 0: float('inf'), -1: float('inf')}
		if nums[0] == 0:
			d[1] = float('inf')
		for (i, p) in enumerate(dp):
			if p == 1:
				d[1] = min(d[1], i)
				res = max(res, i - d[1] + 1)
			elif p == -1:
				d[-1] = min(d[-1], i)
				res = max(res, i - d[-1])
			else:
				d[1] = i + 1
				d[-1] = float('inf')
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		maxProducts = {}
		numLength = len(nums)
		maxSize = 0
		if nums[0] == 0:
			maxProducts[0] = [0, 0]
		elif nums[0] > 0:
			maxProducts[0] = [1, 0]
		else:
			maxProducts[0] = [0, 1]
		maxSize = max(maxSize, maxProducts[0][0])
		for i in range(1, numLength):
			currentNum = nums[i]
			maxProducts[i] = [0, 0]
			if currentNum > 0:
				maxProducts[i][0] = maxProducts[i - 1][0] + 1
				maxProducts[i][1] = maxProducts[i - 1][1] if maxProducts[i - 1][1] == 0 else maxProducts[i - 1][1] + 1
			elif currentNum < 0:
				maxProducts[i][1] = maxProducts[i - 1][0] + 1
				maxProducts[i][0] = maxProducts[i - 1][1] if maxProducts[i - 1][1] == 0 else maxProducts[i - 1][1] + 1
			maxSize = max(maxSize, maxProducts[i][0])
		return maxSize


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(start, first_neg) = (-1, float('inf'))
		(maxi, positive) = (0, 1)
		for (index, value) in enumerate(nums):
			if value == 0:
				(start, first_neg, positive) = (index, float('inf'), 1)
			else:
				positive = positive == (value > 0)
				if positive:
					maxi = max(maxi, index - start)
				else:
					maxi = max(maxi, index - first_neg)
					first_neg = min(first_neg, index)
		return maxi


from typing import List

class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		left_size = []
		left_mult = []
		size = 0
		mult = 0
		for val in nums:
			if val == 0:
				size = 0
				mult = 0
			else:
				size += 1
				mult += 1 if val < 0 else 0
			left_size.append(size)
			left_mult.append(mult)
		right_size = []
		right_mult = []
		size = 0
		mult = 0
		for val in nums[::-1]:
			if val == 0:
				size = 0
				mult = 0
			else:
				size += 1
				mult += 1 if val < 0 else 0
			right_size.append(size)
			right_mult.append(mult)
		right_size = right_size[::-1]
		right_mult = right_mult[::-1]
		ans = 0
		for (idx, val) in enumerate(nums):
			if val == 0:
				continue
			ls = 0
			lm = 0
			if idx > 0:
				ls = left_size[idx - 1]
				lm = left_mult[idx - 1]
			rs = 0
			rm = 0
			if idx < len(nums) - 1:
				rs = right_size[idx + 1]
				rm = right_mult[idx + 1]
			cur = int(val < 0)
			if lm % 2 == 0:
				ans = max(ans, ls)
			if val > 0:
				ans = max(ans, 1)
			if (lm + cur) % 2 == 0:
				ans = max(ans, ls + 1)
			if rm % 2 == 0:
				ans = max(ans, rs)
			if (rm + cur) % 2 == 0:
				ans = max(ans, rs + 1)
			if (lm + cur + rm) % 2 == 0:
				ans = max(ans, ls + rs + 1)
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def _getMaxLen(nums):
			if not nums:
				return 0
			n_ones = sum(nums)
			if n_ones % 2 == 0:
				return len(nums)
			return len(nums) - min(nums.index(1), nums[::-1].index(1)) - 1
		ans = prev = 0
		nums = [0 if i > 0 else 1 if i < 0 else -1 for i in nums]
		while nums:
			try:
				idx = nums.index(-1)
				ans = max(_getMaxLen(nums[:idx]), ans)
				nums = nums[idx + 1:]
			except:
				ans = max(ans, _getMaxLen(nums))
				break
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def conv(n):
			if n > 0:
				return 1
			if n == 0:
				return 0
			return -1
		nums = list(map(conv, nums))
		n = len(nums)

		def check(size):
			if size == 0:
				return True
			if size > n:
				return False
			p = 1
			lo = hi = 0
			while hi < n:
				if nums[hi] == 0:
					p = 1
					lo = hi = hi + 1
					continue
				p *= nums[hi]
				if hi - lo + 1 == size:
					if p > 0:
						return True
					p //= nums[lo]
					lo += 1
				hi += 1
			return False
		res = 0
		(lo, hi) = (0, n)
		while lo <= hi:
			m = (lo + hi) // 2
			(r1, r2) = (check(m), check(m + 1))
			if r1 or r2:
				if r1:
					res = m
				if r2:
					res = m + 1
				lo = m + 2
			else:
				hi = m - 1
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		left = 0
		ans = 0
		from numpy import sign
		while left < len(nums) - ans:
			right = left
			s = 1
			while right < len(nums):
				s *= sign(nums[right])
				if s > 0:
					ans = max(ans, right - left + 1)
				elif s == 0:
					break
				right += 1
			if nums[left] > 0:
				while left < len(nums) and nums[left] > 0:
					left += 1
			else:
				left += 1
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		sublists = []
		i = 0
		while nums and i < len(nums):
			if nums[i]:
				i += 1
			else:
				sublists.append(nums[:i])
				nums = nums[i + 1:]
				i = 0
		sublists.append(nums)
		return max([self.getMaxLenFromNonZero(sublist) for sublist in sublists])

	def getMaxLenFromNonZero(self, nums: List[int]) -> int:
		count = 0
		front = len(nums)
		back = 0
		for i in range(len(nums)):
			if nums[i] < 0:
				count += 1
				if front > i:
					front = i
				back = i
		if count % 2 == 0:
			return len(nums)
		else:
			return len(nums) - min([front + 1, len(nums) - back])


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def _getMaxLen(nums):
			if not nums:
				return 0
			fn = 0
			while fn < len(nums) and nums[fn] > 0:
				fn += 1
			pos = True
			res = 0
			for i in range(len(nums)):
				if nums[i] < 0:
					pos = not pos
				if pos:
					res = max(res, i + 1)
				else:
					res = max(res, i - fn)
			return res
		ans = prev = 0
		while nums:
			try:
				idx = nums.index(0)
				ans = max(_getMaxLen(nums[:idx]), ans)
				nums = nums[idx + 1:]
			except:
				ans = max(ans, _getMaxLen(nums))
				break
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		lastExtraMinus = None
		lastZero = 0
		out = 0
		firstExtraMinus = None
		for (i, n) in enumerate(nums):
			if n < 0:
				lastExtraMinus = None if lastExtraMinus != None else i
				if firstExtraMinus == None:
					firstExtraMinus = i
			if n == 0:
				lastZero = i + 1
				lastExtraMinus = None
				firstExtraMinus = None
			elif lastExtraMinus == None:
				out = max(out, i - lastZero + 1)
			else:
				out = max(out, i - firstExtraMinus)
		return out


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def find_list(nums):
			pos = 0
			neg = 0
			for i in nums:
				if i > 0:
					pos += 1
				if i < 0:
					neg += 1
			if neg % 2 == 0:
				print(len(nums))
			else:
				first = 0
				last = len(nums) - 1
				while first <= last:
					if nums[first] < 0:
						nums = nums[first + 1:]
						break
					else:
						first += 1
					if nums[last] < 0:
						nums = nums[:last]
						break
					else:
						last -= 1
			return len(nums)
		ans = 0
		zero = 0
		remove = 0
		for i in nums:
			if i == 0:
				zero += 1
		while zero != 0:
			first = 0
			last = len(nums) - 1
			while first <= last:
				if nums[first] == 0:
					remove_list = nums[:first]
					ans = max(ans, find_list(remove_list))
					nums = nums[first + 1:]
					break
				else:
					first += 1
				if nums[last] == 0:
					remove_list = nums[last + 1:]
					ans = max(ans, find_list(remove_list))
					nums = nums[:last]
					break
				else:
					last -= 1
			zero = zero - 1
		return max(ans, find_list(nums))


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def max_len(i, j):
			if i > j:
				return 0
			res = 1
			for k in range(i, j + 1):
				res *= nums[k]
			if res > 0:
				return j - i + 1
			l = i
			r = j
			while nums[l] > 0:
				l += 1
			while nums[r] > 0:
				r -= 1
			return max(j - l, r - i)
		prev = 0
		res = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				res = max(res, max_len(prev, i - 1))
				prev = i + 1
		res = max(res, max_len(prev, len(nums) - 1))
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		zeroIdx = []
		for (idx, num) in enumerate(nums):
			if num == 0:
				zeroIdx += (idx,)
		start = 0
		ans = 0
		for idx in zeroIdx:
			if idx - start > 0:
				ans = max(ans, self.maxLength(nums, [start, idx], idx))
			start = idx + 1
		ans = max(ans, self.maxLength(nums, [start, len(nums)], len(nums)))
		return ans

	def maxLength(self, nums, arr, N):
		product = 1
		Len = 0
		for i in range(arr[0], arr[1]):
			product *= nums[i]
		if product >= 0:
			return arr[1] - arr[0]
		for i in range(arr[0], arr[1]):
			if nums[i] < 0:
				Len = max(Len, max(N - i - 1, i - arr[0]))
		return Len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		nums += [0]
		max_so_far = 0
		N = len(nums)
		res = 1
		(last_zero, last_neg, first_neg, last_pos) = (0, -1, N, -1)
		for i in range(N):
			res *= nums[i]
			if nums[i] == 0:
				if res > 0:
					max_so_far = max(max_so_far, i - last_zero + 1)
				else:
					max_so_far = max(max_so_far, i - first_neg, last_pos - last_zero + 1)
				last_zero = i + 1
				first_neg = N
				last_pos = last_zero if i < N - 1 and nums[i + 1] > 0 else last_zero - 1
				res = 1
			elif nums[i] < 0 and first_neg == N:
				first_neg = i + 1
			elif res > 0:
				last_pos = i
		return max_so_far


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(res, n, q, cur) = (0, len(nums), [], 1)

		def extract(q, cur, res):
			if cur > 0:
				res = max(res, len(q))
			else:
				i = 0
				while i < len(q):
					if q[i] < 0:
						break
					i += 1
				res = max(res, len(q) - i - 1)
				i = len(q) - 1
				while i >= 0:
					if q[i] < 0:
						break
					i -= 1
				res = max(res, i)
			return res
		for v in nums:
			if v != 0:
				q.append(v)
				cur *= v
			else:
				res = extract(q, cur, res)
				cur = 1
				q = []
		return extract(q, cur, res)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		start_neg = -1
		end_neg = -1
		start_idx = -1
		end_idx = -1
		acc_product = None
		ans = 0
		nums += [0]
		for (idx, num) in enumerate(nums):
			if num == 0:
				if start_idx == -1:
					continue
				if acc_product > 0:
					ans = max(ans, end_idx - start_idx + 1)
				elif start_neg - start_idx < end_idx - end_neg:
					ans = max(ans, end_idx - start_neg - 1 + 1)
				else:
					ans = max(ans, end_neg - start_idx - 1 + 1)
				start_idx = -1
				end_idx = -1
				acc_product = None
				start_neg = -1
				end_neg = -1
			else:
				if start_idx < 0:
					start_idx = idx
				end_idx = idx
				if not acc_product:
					acc_product = 1
				acc_product *= num
				if num < 0:
					end_neg = idx
					if start_neg < 0:
						start_neg = idx
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		target = []
		t = []
		for n in nums:
			if n != 0:
				t.append(n)
			else:
				target.append(t.copy())
				t = []
		target.append(t.copy())

		def find(nums):
			if len(nums) == 0:
				return 0
			positive_ma = -1
			positive_min = -1
			negtive_ma = -1
			negtive_mi = -1
			t = 1
			for i in range(len(nums)):
				t *= nums[i]
				if t > 0 and positive_min == -1:
					positive_ma = i
					positive_min = i
				elif t > 0 and positive_min != -1:
					positive_ma = i
				if t < 0 and negtive_mi == -1:
					negtive_mi = i
					negtive_ma = i
				elif t < 0 and negtive_mi != -1:
					negtive_ma = i
			p_l = 0
			n_l = 0
			if positive_min != -1:
				p_l = positive_ma + 1
			if negtive_mi != -1 and negtive_mi != negtive_ma:
				n_l = negtive_ma - negtive_mi
			print((positive_ma, positive_min, negtive_ma, negtive_mi))
			return max(p_l, n_l)
		result = 0
		for t in target:
			result = max(result, find(t))
		return result


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(res, q, n, start) = (0, [], len(nums), 0)
		for (i, v) in enumerate(nums):
			if v == 0:
				start = i + 1
				q = []
			elif v < 0:
				q.append(i)
			if len(q) & 1:
				res = max(res, i - q[0], q[-1] - start)
			else:
				res = max(res, i - start + 1)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(res, curr, prevp, prevn) = (0, 1, 0, None)
		for (i, num) in enumerate(nums, 1):
			if num == 0:
				(curr, prevp, prevn) = (1, i, None)
			else:
				curr *= num
				if curr > 0:
					res = max(res, i - prevp)
				elif prevn == None:
					prevn = i
				else:
					res = max(res, i - prevn)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(pos, neg) = (-1, None)
		(P, Max) = (1, 0)
		for i in range(len(nums)):
			P *= nums[i]
			if P == 0:
				(pos, neg) = (i, None)
				P = 1
			elif P < 0 and neg is None:
				neg = i
			elif P < 0:
				Max = max(Max, i - neg)
			else:
				Max = max(Max, i - pos)
		return Max


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		product = 1
		count = 0
		firstNegative = -1
		maxCount = 0
		for i in range(len(nums)):
			if nums[i] < 0:
				if firstNegative == -1:
					firstNegative = i
			if nums[i] == 0:
				count = 0
				product = 1
				firstNegative = -1
			else:
				product *= nums[i]
				count += 1
				if product > 0:
					maxCount = max(maxCount, count)
				elif firstNegative != -1:
					maxCount = max(maxCount, i - firstNegative)
		return maxCount


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		subarrays = []
		temp = []
		for i in range(len(nums)):
			if nums[i] == 0:
				subarrays.append(temp.copy())
				temp = []
			else:
				temp += [nums[i]]
		subarrays.append(temp.copy())

		def util(a):
			p = 1
			for i in a:
				p *= i
			if p > 0:
				return len(a)
			else:
				i = 0
				while a[i] > 0:
					i += 1
				ans1 = len(a) - i - 1
				j = len(a) - 1
				while a[j] > 0:
					j -= 1
				ans2 = j
				return max(ans1, ans2)
		maxm = -1
		for i in subarrays:
			maxm = max(maxm, util(i))
		return maxm


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def check(arr) -> int:
			if not arr:
				return 0
			pos = neg = -1
			pre_prod = 1
			res = 0
			for (i, a) in enumerate(arr):
				pre_prod *= a
				if pre_prod > 0:
					if pos == -1:
						pos = i
					res = i + 1
				else:
					if neg == -1:
						neg = i
					res = max(res, i - neg)
			return res
		res = i = j = 0
		while j < len(nums):
			while j < len(nums) and nums[j] == 0:
				j += 1
			i = j
			while j < len(nums) and nums[j] != 0:
				j += 1
			res = max(res, check(nums[i:j]))
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		cp = 1
		fp = -1
		fn = None
		ans = 0
		for (i, n) in enumerate(nums):
			cp = n * cp
			if cp < 0:
				if fn is None:
					fn = ln = i
				else:
					ln = i
				ans = max(ln - fn, ans)
			elif cp > 0:
				lp = i
				ans = max(lp - fp, ans)
			if n == 0:
				cp = 1
				fp = i
				fn = None
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		prod = 1
		(pos, neg) = (-1, None)
		ans = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				(pos, neg) = (i, None)
				prod = 1
			else:
				prod *= nums[i]
				if prod > 0:
					ans = max(ans, i - pos)
				else:
					if neg == None:
						neg = i
					ans = max(ans, i - neg)
		return ans


from functools import reduce

class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		splitted = sorted(self.split(nums), key=lambda x: len(x), reverse=True)
		v = 0
		for sp in splitted:
			if len(sp) < v:
				break
			v = max(v, self.solve(sp))
		return v

	def split(self, nums):
		prev = None
		ans = []
		hit = False
		for (i, n) in enumerate(nums):
			if n == 0 and prev is not None:
				ans.append(nums[prev:i])
				hit = True
				prev = None
			elif prev is None and n != 0:
				prev = i
		if not hit:
			return [[n for n in nums if n != 0]]
		if prev is not None and prev != len(nums) - 1:
			ans.append(nums[prev:len(nums)])
		return ans

	def solve(self, nums):
		N = len(nums)
		prod = reduce(lambda x, y: x * y, nums, 1)
		if prod > 0:
			return N
		for i in range(N // 2):
			if nums[i] < 0 or nums[N - 1 - i] < 0:
				return N - i - 1
		return 0


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ans = 0
		fn = -1
		s = -1
		p = 1
		for i in range(len(nums)):
			if nums[i] == 0:
				fn = -1
				s = -1
				p = 1
			else:
				if s == -1:
					s = i
				p *= nums[i]
				if p < 0 and fn == -1:
					fn = i
				if p < 0:
					ans = max(ans, i - s + 1 - (fn - s + 1))
				elif p > 0:
					ans = max(ans, i - s + 1)
		return ans


class Solution:

	def calc(self, neg: List[int], i: int) -> int:
		if len(neg) % 2 == 0:
			return i
		else:
			return max(i - neg[0] - 1, neg[-1])

	def getMaxLen(self, nums: List[int]) -> int:
		ml = 0
		while True:
			neg = []
			for (idx, i) in enumerate(nums):
				if i == 0:
					ml = max(self.calc(neg, idx), ml)
					nums = nums[idx + 1:]
					break
				elif i < 0:
					neg.append(idx)
			else:
				if nums != []:
					ml = max(ml, self.calc(neg, idx + 1))
				break
		return ml


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		N = len(nums)
		firstNegIdx = math.inf
		prevZeroIdx = -1
		curr = 1
		res = 0
		for (i, n) in enumerate(nums):
			if n == 0:
				prevZeroIdx = i
				firstNegIdx = math.inf
				curr = 1
			else:
				curr *= n
				if curr > 0:
					res = max(res, i - prevZeroIdx)
				else:
					firstNegIdx = min(firstNegIdx, i)
					res = max(res, i - firstNegIdx)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		accLast = 1
		accCurr = 1
		lastpos = 0
		lastnegative = -1
		res = 0
		dic = {}
		for i in range(len(nums)):
			accCurr = accLast * nums[i]
			if accCurr == 0:
				lastpos = i + 1
				lastnegative = -1
				accCurr = 1
			elif accCurr > 0:
				if lastpos != -1:
					res = max(res, i + 1 - lastpos)
			elif lastnegative != -1:
				res = max(res, i + 1 - lastnegative)
			else:
				lastnegative = i + 1
			accLast = accCurr
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		fpos = -1
		fneg = -1
		best = 0
		cur = 1
		for i in range(len(nums)):
			n = nums[i]
			if n == 0:
				fpos = i
				fneg = -1
				cur = 1
			else:
				if fneg == -1 and n < 0:
					fneg = i
				cur *= n
				if cur > 0:
					best = max(best, i - fpos)
				elif cur < 0 and fneg != -1:
					best = max(best, i - fneg)
		return best


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		max_len = 0
		start = -1
		is_pos = True
		for i in range(len(nums) + 1):
			if i == len(nums) or nums[i] == 0:
				if is_pos:
					max_len = max(max_len, i - start - 1)
				else:
					tmp = start + 1
					while tmp < i:
						if nums[tmp] < 0:
							break
						tmp += 1
					max_len = max(max_len, i - tmp - 1)
				start = i
				is_pos = True
			else:
				if nums[i] < 0:
					is_pos = not is_pos
				if is_pos:
					max_len = max(max_len, i - start)
		return max_len


class Solution:

	def _getMaxLen(self, nums: List[int]) -> int:
		lz = [i for (i, v) in enumerate(nums) if v < 0]
		ts = len(nums)
		if len(lz) % 2 == 0:
			return ts
		if len(lz) == 1:
			lz = [lz[0], lz[0]]
		ls = lz[-1]
		rs = ts - (lz[0] + 1)
		if ls > rs:
			return ls
		return rs

	def getMaxLen(self, nums: List[int]) -> int:
		r = 0
		zero1 = 0
		try:
			zero1 = nums.index(0)
			r = self._getMaxLen(nums[:zero1])
			nums = nums[zero1 + 1:]
			while True:
				zero2 = nums.index(0)
				r2 = self._getMaxLen(nums[:zero2])
				if r2 > r:
					r = r2
				zero1 = zero2
				nums = nums[zero1 + 1:]
		except ValueError:
			pass
		r2 = self._getMaxLen(nums)
		if r2 > r:
			r = r2
		return r


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if not nums:
			return 0
		last_neg_i = -1
		acc_product = 1
		bound = -1
		max_len = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				acc_product = 1
				last_neg_i = -1
				bound = i
				continue
			acc_product = acc_product * nums[i]
			if last_neg_i == -1 and acc_product < 0:
				last_neg_i = i
			if acc_product < 0:
				max_len = max(max_len, i - last_neg_i)
			else:
				max_len = max(max_len, i - bound)
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		max_len = 0
		last_idx = float('inf')
		(curr_st, curr_prod) = (0, 1)
		for ed in range(len(nums)):
			if nums[ed] == 0:
				curr_prod = 1
				curr_st = ed + 1
				last_idx = float('inf')
				continue
			else:
				curr_prod *= nums[ed]
			if curr_prod > 0:
				max_len = max(max_len, ed - curr_st + 1)
			elif curr_prod < 0:
				max_len = max(max_len, ed - last_idx)
				if last_idx == float('inf'):
					last_idx = ed
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		first_neg = None
		last_neg = None
		first_pos = None
		cum_prod = 1
		max_len = 0
		last_zero_idx = 0
		for (idx, val) in enumerate(nums):
			if val == 0:
				first_neg = None
				last_neg = None
				first_pos = None
				cum_prod = 1
				last_zero_idx = idx + 1
			else:
				cum_prod *= val
				if cum_prod > 0:
					max_len = max(max_len, idx - last_zero_idx + 1)
				else:
					if first_neg is None:
						first_neg = idx
					last_neg = idx
					max_len = max(max_len, last_neg - first_neg)
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		i = 0
		negatives = [-1, -1]
		p = 1
		ans = 0
		for (j, n) in enumerate(nums):
			if not n:
				p = 1
				i = j + 1
				negatives = [-1, -1]
			else:
				p *= n
				if n < 0:
					if negatives[0] < 0:
						negatives[0] = j
					negatives[1] = j
				if p > 0:
					ans = max(ans, j - i + 1)
				else:
					ans = max(ans, negatives[1] - i, j - negatives[0])
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def helper(nums):
			if len(nums) == 0:
				return 0
			pre_prod = 1
			N = len(nums)
			first_neg = -1
			res = 0
			for i in range(N):
				pre_prod *= nums[i]
				if pre_prod > 0:
					res = max(res, i + 1)
				elif first_neg == -1 and pre_prod < 0:
					first_neg = i
				elif pre_prod < 0:
					res = max(res, i - first_neg)
			return res
		num = []
		res = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				res = max(res, helper(num))
				num = []
			else:
				num.append(nums[i])
		res = max(res, helper(num))
		return res


class Solution:

	def getMaxLen(self, A: List[int]) -> int:
		n = len(A)
		lastZ = -1
		lastN = n
		cur = 1
		res = 0
		for (i, a) in enumerate(A):
			cur *= a
			if cur == 0:
				lastZ = i
				lastN = n
				cur = 1
			elif cur > 0:
				res = max(res, i - lastZ)
			else:
				lastN = min(lastN, i)
				res = max(res, i - lastN)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(max_len, start, product, first_minus_index) = (0, 0, 1, -1)
		for (i, n) in enumerate(nums):
			if n == 0:
				(start, product, first_minus_index) = (i + 1, 1, -1)
			else:
				if n < 0 and first_minus_index == -1:
					first_minus_index = i
				product *= n
				if n > 0:
					max_len = max(max_len, 1)
				if product > 0:
					max_len = max(max_len, i - start + 1)
				if product < 0 and first_minus_index != -1:
					max_len = max(max_len, i - first_minus_index)
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		s = 0
		fn = -1
		ln = -1
		cn = 0
		res = 0
		for (i, v) in enumerate(nums):
			if v == 0:
				end = i - 1
				if cn % 2 == 0:
					res = max(res, end - s + 1)
				else:
					res = max(res, end - fn, ln - s)
				s = i + 1
				fn = -1
				ln = -1
				cn = 0
			elif v < 0:
				if fn == -1:
					fn = ln = i
				else:
					ln = i
				cn += 1
		end = len(nums) - 1
		if cn % 2 == 0:
			res = max(res, end - s + 1)
		else:
			res = max(res, end - fn, ln - s)
		return res


class Solution:

	def getMaxLen(self, a: List[int]) -> int:
		n = len(a)
		ans = 0
		neg = -1
		zero = -1
		cnt = 0
		for (i, x) in enumerate(a):
			if x == 0:
				neg = zero = i
				cnt = 0
			elif x < 0:
				if neg == zero:
					neg = i
				cnt += 1
			if cnt % 2 == 0:
				ans = max(ans, i - zero)
			else:
				ans = max(ans, i - neg)
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		left_pos = 0
		left_neg = sys.maxsize
		ans = 0
		cp = 1
		for (i, num) in enumerate(nums):
			if num == 0:
				cp = 1
				left_pos = i + 1
				left_neg = sys.maxsize
			else:
				cp *= num
				if cp > 0:
					ans = max(ans, i - left_pos + 1)
				else:
					ans = max(ans, i - left_neg)
				if cp < 0 and left_neg == sys.maxsize:
					left_neg = i
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		f = [0, 0]
		ans = 0
		for i in range(len(nums)):
			if nums[i] < 0:
				f = [f[1] + 1 if f[1] > 0 else 0, f[0] + 1]
			elif nums[i] > 0:
				f = [f[0] + 1, f[1] + 1 if f[1] > 0 else 0]
			else:
				f = [0, 0]
			ans = max(ans, f[0])
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		positive_index = -1
		negative_index = -1
		sums = 1
		result = 0
		for i in range(len(nums)):
			if sums * nums[i] < 0:
				sums = -1
			elif sums * nums[i] > 0:
				sums = 1
			if nums[i] == 0:
				positive_index = i
				negative_index = -1
				sums = 1
			elif sums > 0:
				result = max(result, i - positive_index)
			elif negative_index == -1:
				negative_index = i
			else:
				result = max(result, i - negative_index)
				print(result)
		return result


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		N = len(nums)
		ans = 0
		i = j = 0
		while i < N:
			if nums[i] == 0:
				i += 1
				continue
			j = i
			while j < N and nums[j]:
				j += 1
			negs = 0
			firstneg = lastneg = None
			for k in range(i, j):
				if nums[k] < 0:
					negs += 1
					if firstneg is None:
						firstneg = k
					lastneg = k
			if negs % 2 == 0:
				ans = max(ans, j - i)
			else:
				ans = max(ans, firstneg - i, j - i - 1 - (firstneg - i))
				ans = max(ans, lastneg - i, j - i - 1 - (lastneg - i))
			i = j
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		result = 0
		for r in [list(range(0, len(nums))), list(range(len(nums) - 1, -1, -1))]:
			cur_len = 0
			cur_sign = 1
			for i in r:
				if nums[i] > 0:
					cur_len += 1
					result = max(result, cur_sign * cur_len)
				elif nums[i] == 0:
					cur_len = 0
					cur_sign = 1
				else:
					cur_len += 1
					cur_sign = -cur_sign
					result = max(result, cur_sign * cur_len)
		return result


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		first_neg = -1
		last_neg = -1
		pos = True
		start = 0
		best = 0
		n = len(nums)
		for (i, num) in enumerate(nums):
			if num == 0:
				if pos:
					best = max(best, i - start)
				elif first_neg >= start:
					best = max(best, i - first_neg - 1, last_neg - start)
				start = i + 1
				pos = True
			elif num < 0:
				last_neg = i
				if first_neg < start:
					first_neg = i
				pos = not pos
		if pos:
			best = max(best, n - start)
		elif first_neg >= start:
			best = max(best, n - first_neg - 1, last_neg - start)
		return best


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def helper(array):
			if len(array) == 0:
				return 0
			result = 0
			pos = 0
			neg = 0
			for n in array:
				if n > 0:
					(pos, neg) = (pos + 1, neg + 1 if neg > 0 else 0)
				if n < 0:
					(pos, neg) = (neg + 1 if neg > 0 else 0, pos + 1)
				result = max(result, pos)
			return result
		arrays = []
		subarray = []
		for n in nums:
			if n == 0:
				idx = 0
				arrays.append(subarray)
				subarray = []
				continue
			subarray.append(n)
		if len(subarray) > 0:
			arrays.append(subarray)
		maxlen = 0
		for (i, array) in enumerate(arrays):
			maxlen = max(maxlen, helper(array))
		return maxlen


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		start = 0
		end = 0
		count_negative = 0
		max_len = 0
		while end < len(nums):
			if nums[end] == 0:
				if count_negative % 2 != 0:
					while nums[start] > 0:
						start += 1
					max_len = max(max_len, end - start - 1)
				start = end = end + 1
				count_negative = 0
			else:
				if nums[end] < 0:
					count_negative += 1
				if count_negative % 2 == 0:
					max_len = max(max_len, end - start + 1)
				if end == len(nums) - 1 and count_negative % 2 == 1:
					while nums[start] > 0:
						start += 1
					max_len = max(max_len, end - start)
				end += 1
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		count_of_negative = 0
		start = 0
		max_length = 0

		def evaluate_sub_array(begin, end, count_of_negative):
			if count_of_negative % 2 == 0:
				return end - begin + 1
			else:
				first_negative = len(nums)
				last_negative = -1
				for i in range(begin, end + 1):
					if nums[i] < 0:
						if first_negative == len(nums):
							first_negative = i
							last_negative = i
						else:
							last_negative = i
			return max(end - first_negative, last_negative - begin)
		start = 0
		array = []
		count_of_negative = 0
		for index in range(len(nums)):
			if nums[index] < 0:
				count_of_negative += 1
			if nums[index] == 0:
				array.append(evaluate_sub_array(start, index - 1, count_of_negative))
				count_of_negative = 0
				start = index + 1
		array.append(evaluate_sub_array(start, len(nums) - 1, count_of_negative))
		return max(array)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dic = {1: -1}
		temp = 1
		res = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				dic = {1: i}
				temp = 1
				continue
			if nums[i] < 0:
				temp = -temp
			if not dic.get(temp) is None:
				res = max(res, i - dic[temp])
			else:
				dic[temp] = i
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def max_len(nums):
			negs = [i for (i, x) in enumerate(nums) if x < 0]
			n = len(nums)
			if len(negs) % 2 == 0:
				return n
			else:
				return max(n - (negs[0] + 1), negs[-1])
		from copy import deepcopy
		chunks = []
		chunk = []
		for x in nums:
			if x == 0 and chunk:
				chunks.append(deepcopy(chunk))
				chunk.clear()
			elif x:
				chunk.append(x)
		chunks.append(chunk)
		print(chunks)
		return max(map(max_len, chunks))


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		m = 0
		neg = 0
		pos = 0
		positiveBeforeFirstNeg = 0
		pos2 = 0
		for i in nums:
			if i == 0:
				if neg > 0 and neg % 2 != 0:
					neg -= 1
				if positiveBeforeFirstNeg < pos2 and neg > 2:
					pos -= positiveBeforeFirstNeg
					pos += pos2
				m = max(max(pos, pos2) + neg, m)
				(neg, pos, pos2) = (0, 0, 0)
			elif i < 0:
				if neg == 0:
					positiveBeforeFirstNeg = pos
				neg += 1
				if neg % 2 == 0:
					pos += pos2
					pos2 = 0
			elif neg % 2 != 0:
				pos2 += 1
			else:
				pos += 1
		if positiveBeforeFirstNeg < pos2 and neg > 2:
			pos -= positiveBeforeFirstNeg
			pos += pos2
		if neg > 0 and neg % 2 != 0:
			neg -= 1
		m = max(max(pos, pos2) + neg, m)
		return m


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		carry_len = 0
		left_neg = 0
		max_len = 0
		str_ptr = -1
		for (idx, n) in enumerate(nums):
			if n < 0:
				left_neg += 1
			carry_len += 1
			if n == 0:
				max_len = max(max_len, 0)
				carry_len = 0
				left_neg = 0
			else:
				max_len = max(max_len, 1 if n > 0 else 0, idx - str_ptr - 1, carry_len if left_neg % 2 == 0 else 0)
			if left_neg == 0:
				str_ptr = idx
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(start, curnegcnt, res, fnegpos, lnegpos) = (0, 0, 0, 0, 0)
		flag = True
		(i, j) = (0, len(nums))
		while i < j:
			if nums[i] == 0:
				flag = True
				i += 1
				start = i
				curnegcnt = 0
				continue
			if nums[i] < 0:
				if flag:
					flag = False
					fnegpos = i
				lnegpos = i
				curnegcnt += 1
			if curnegcnt == 0 or curnegcnt % 2 == 0:
				res = max(res, i - start + 1)
			else:
				res = max(res, lnegpos - start, i - fnegpos)
			i += 1
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(pos, neg) = (0, 0)
		asr = 0
		for num in nums:
			if num == 0:
				(pos, neg) = (0, 0)
			elif num > 0:
				pos += 1
				neg = neg + 1 if neg else 0
			else:
				n_pos = neg + 1 if neg else 0
				n_neg = pos + 1 if pos else 1
				(pos, neg) = (n_pos, n_neg)
			asr = max(asr, pos)
		return asr


def sgn(n):
	if n > 0:
		return +1
	elif n < 0:
		return -1
	else:
		return 0

def split_0(arr):
	arr_buffer = []
	for elem in arr:
		if elem != 0:
			arr_buffer.append(elem)
		else:
			yield arr_buffer
			arr_buffer = []
	assert len(arr_buffer) == 0

def partial_products(arr):
	prod = 1
	yield prod
	for elem in arr:
		prod *= elem
		yield prod

def get_subarr_max_len(arr):
	first_index = {}
	max_len = 0
	for (i, prod) in enumerate(partial_products(arr)):
		first_index.setdefault(prod, i)
		max_len = max(max_len, i - first_index[prod])
	return max_len

def get_max_len(arr):
	arr = [sgn(x) for x in arr]
	arr.append(0)
	if len(arr) == 0:
		return 0
	return max((get_subarr_max_len(subarr) for subarr in split_0(arr)))

class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		return get_max_len(nums)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		if not n:
			return -1
		pos = 0
		neg = 0
		answer = 0
		for num in nums:
			if num == 0:
				answer = max(answer, pos)
				pos = neg = 0
				continue
			if num > 0:
				pos += 1
				neg += 1 if neg else 0
			else:
				orig_pos = pos
				pos = neg + 1 if neg else 0
				neg = orig_pos + 1 if orig_pos else 1
			answer = max(answer, pos)
		return answer


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dct = {0: -1}
		count = 0
		res = 0
		for (i, num) in enumerate(nums):
			if num < 0:
				count += 1
				dct[count] = i
			elif num == 0:
				dct = {0: i}
				count = 0
			if count % 2 == 0:
				res = max(res, i - dct[0])
			else:
				t1 = i - dct[1]
				t2 = 0
				if num < 0:
					t2 = i - 1 - dct[0]
				res = max(res, max(t1, t2))
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if nums[-1] != 0:
			nums.append(0)
		n = len(nums)
		first_0 = -1
		last_0 = -1
		cnt_neg = 0
		first_neg = -1
		last_neg = -1
		res = 0
		for (i, e) in enumerate(nums):
			if e < 0:
				cnt_neg += 1
				if first_neg == -1:
					first_neg = i
				last_neg = i
			elif e == 0:
				last_0 = i
				if cnt_neg % 2 == 0:
					res = max(res, last_0 - first_0 - 1)
				else:
					res = max(res, last_neg - first_0 - 1, last_0 - first_neg - 1)
				cnt_neg = 0
				first_0 = last_0
				first_neg = -1
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		a = 0
		p = 0
		n = 0
		r = -1
		for x in nums:
			(p, n, r) = ((x < 0) * p + (x > 0) * (p + 1), (x < 0) * (n + 1) + (x > 0) * n, (x < 0) * (r < 0) * p + (x < 0) * (r >= 0) * r + (x > 0) * r - (x == 0))
			a = max(a, p + n - n % 2 * (r + 1))
		return a


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		next_zero_or_end = [0] * (len(nums) + 1)
		next_idx = len(nums)
		last_negative = [0] * (len(nums) + 1)
		negative_idx = None
		state = 0
		for i in range(len(nums) - 1, -1, -1):
			num = nums[i]
			if num == 0:
				next_idx = i
				state = 0
			next_zero_or_end[i] = next_idx
			if state == 0 and num < 0:
				negative_idx = i
				state = 1
			last_negative[i] = negative_idx
		ne_nums = [0] * (len(nums) + 1)
		for (i, num) in enumerate(nums):
			ne_nums[i] = ne_nums[i - 1] + (1 if num < 0 else 0)
		res = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				continue
			j = next_zero_or_end[i] - 1
			if (ne_nums[j] - ne_nums[i - 1]) % 2 == 0:
				res = max(res, j - i + 1)
			else:
				j = last_negative[i] - 1
				res = max(res, j - i + 1)
		return res


class Node:

	def __init__(self, size):
		self.size = size
		self.left = None
		self.right = None

class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		nodes = []
		roots = []
		curr_size = 0
		prev = None
		for i in range(len(nums)):
			if nums[i] > 0:
				curr_size += 1
			else:
				node = Node(curr_size)
				nodes.append(node)
				if prev:
					prev.right = node
					node.left = prev
				else:
					roots.append(node)
				if nums[i] != 0:
					prev = node
				else:
					prev = None
				curr_size = 0
		node = Node(curr_size)
		if prev:
			prev.right = node
			node.left = prev
		else:
			roots.append(node)
		longest = 0
		for node in roots:
			first_count = node.size
			second_count = 0 if not node.right else node.right.size
			curr_node = node.right.right if node.right else None
			ind = 0
			while curr_node:
				if ind == 0:
					first_count += curr_node.size + curr_node.left.size + 2
					ind = 1
				else:
					second_count += curr_node.size + curr_node.left.size + 2
					ind = 0
				curr_node = curr_node.right
			longest = max(longest, first_count, second_count)
		return longest


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		pos = [0 for _ in range(len(nums))]
		neg = [0 for _ in range(len(nums))]
		if nums[0] > 0:
			pos[0] = 1
		elif nums[0] < 0:
			neg[0] = 1
		out = pos[0]
		for i in range(1, len(nums)):
			if nums[i] > 0:
				pos[i] = 1 + pos[i - 1]
				neg[i] = 1 + neg[i - 1] if neg[i - 1] else 0
			elif nums[i] < 0:
				pos[i] = 1 + neg[i - 1] if neg[i - 1] else 0
				neg[i] = 1 + pos[i - 1]
			out = max(out, pos[i])
		return out


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def getMaxLenNonzero(arr):
			neg = []
			for (i, num) in enumerate(arr):
				if num < 0:
					neg.append(i)
			if len(neg) % 2 == 0:
				return len(arr)
			if len(neg) == 1:
				return max(neg[0], len(arr) - neg[-1] - 1)
			return max(neg[-1], len(arr) - neg[0] - 1)
		currArr = []
		ans = 0
		for num in nums:
			if num != 0:
				currArr.append(num)
			else:
				ans = max(ans, getMaxLenNonzero(currArr))
				currArr = []
		if currArr:
			ans = max(ans, getMaxLenNonzero(currArr))
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = [0] * len(nums)
		for i in range(len(dp)):
			dp[i] = [0, 0]
		ans = 0
		for (i, v) in enumerate(nums):
			if v > 0:
				dp[i][0] = 1 + dp[i - 1][0]
				if dp[i - 1][1]:
					dp[i][1] = 1 + dp[i - 1][1]
			if v < 0:
				if dp[i - 1][1]:
					dp[i][0] = 1 + dp[i - 1][1]
				dp[i][1] = 1 + dp[i - 1][0]
			ans = max(ans, dp[i][0])
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		A = nums
		n = len(A)
		dp = [[0, 0] for i in range(n + 1)]
		max_len = 0
		for i in range(1, n + 1):
			if A[i - 1] > 0:
				dp[i][0] = dp[i - 1][0] + 1
				dp[i][1] = dp[i - 1][1] + 1 if dp[i - 1][1] != 0 else 0
			elif A[i - 1] < 0:
				dp[i][0] = dp[i - 1][1] + 1 if dp[i - 1][1] != 0 else 0
				dp[i][1] = dp[i - 1][0] + 1
			else:
				dp[i][0] = 0
				dp[i][1] = 0
			max_len = max(max_len, dp[i][0])
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ret = 0
		total = 0
		acc = 1
		start = -1
		first = -1
		last = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				if acc > 0:
					ret = max(total, ret)
				else:
					ret = max(ret, first - 1, total - first, last - 1, total - last)
				start = i
				acc = 1
				total = 0
				first = -1
				last = 0
			else:
				total += 1
				acc = acc * (1 if nums[i] > 0 else -1)
				if nums[i] < 0:
					if first == -1:
						first = i - start
					last = 0
				last += 1
		if acc > 0:
			ret = max(total, ret)
		else:
			ret = max(ret, first - 1, total - first, last - 1, total - last)
		return ret


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		listt = []
		a = -1
		for i in range(len(nums)):
			if nums[i] == 0:
				listt.append(nums[a + 1:i])
				a = i
		listt.append(nums[a + 1:])
		while [] in listt:
			listt.remove([])
		if listt == []:
			return 0
		recordlist = {}
		for i in range(len(listt)):
			firstneg = -1
			begneg = -1
			recordlist[i] = 0
			for m in range(len(listt[i])):
				if listt[i][m] < 0 and firstneg == -1:
					firstneg = m
					if begneg == -1:
						begneg = m
					continue
				if listt[i][m] < 0 and firstneg != -1:
					firstneg = -1
			if firstneg == -1:
				recordlist[i] = len(listt[i])
			else:
				recordlist[i] = max([firstneg, len(listt[i]) - firstneg - 1, begneg, len(listt[i]) - begneg - 1])
		m = []
		for i in list(recordlist.values()):
			m.append(i)
		return max(m)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		for i in nums:
			if i > 0:
				i = 1
			elif i < 0:
				i = -1
		arrays = []
		end = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				arrays.append(nums[end:i])
				end = i + 1
		arrays.append(nums[end:])
		maximum = 0
		for arr in arrays:
			maxi = 0
			neg = 0
			first = -1
			for i in range(len(arr)):
				if arr[i] < 0:
					neg += 1
					if first == -1:
						first = i + 1
					last = i
			if neg % 2 == 0:
				maxi = len(arr)
			else:
				subA = len(arr) - first
				subB = last
				maxi = max(subA, subB)
			maximum = max(maximum, maxi)
		return maximum


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def helper(nums):
			result = 0
			positiveSoFar = 0
			negativeSoFar = 0
			for i in range(len(nums)):
				if nums[i] == 0:
					positiveSoFar = 0
					negativeSoFar = 0
				elif nums[i] > 0:
					positiveSoFar += 1
					if negativeSoFar > 0:
						negativeSoFar += 1
				elif nums[i] < 0:
					if negativeSoFar > 0:
						positiveSoFar = max(negativeSoFar, positiveSoFar) + 1
						negativeSoFar = 0
					else:
						negativeSoFar = positiveSoFar + 1
						positiveSoFar = 0
				result = max(result, positiveSoFar)
			return result
		return max(helper(nums), helper(nums[::-1]))


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = []
		for num in nums:
			if num == 0:
				dp.append(0)
			elif num > 0:
				dp.append(1)
			else:
				dp.append(-1)
		for i in range(1, len(dp)):
			if dp[i - 1] == 0:
				continue
			else:
				dp[i] *= dp[i - 1]
		print(dp)
		dic = {}
		res = 0
		zero = -1
		for (i, num) in enumerate(dp):
			if num > 0:
				if 1 not in dic:
					res = max(res, i - zero)
					dic[1] = i
				else:
					res = max(res, i - dic[1] + 1, i - zero)
			elif num == 0:
				dic = {}
				zero = i
			elif -1 not in dic:
				dic[-1] = i
			else:
				res = max(res, i - dic[-1])
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		(numPos, numNeg, res) = (0, 0, 0)
		for i in range(len(nums)):
			if nums[i] > 0:
				numPos += 1
				if numNeg > 0:
					numNeg += 1
			elif nums[i] < 0:
				(numPosTmp, numNegTmp) = (numPos, numNeg)
				if numPosTmp > 0:
					numNeg = numPosTmp + 1
				else:
					numNeg = 1
				if numNegTmp > 0:
					numPos = numNegTmp + 1
				else:
					numPos = 0
			else:
				numNeg = 0
				numPos = 0
			res = max(res, numPos)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if not nums:
			return 0
		splittedArrays = []
		currentArray = []
		negCount = 0
		for num in nums:
			if num == 0:
				if len(currentArray) > 0:
					splittedArrays.append((currentArray, negCount))
				currentArray = []
				negCount = 0
			else:
				currentArray.append(num)
				negCount += 1 if num < 0 else 0
		if len(currentArray) > 0:
			splittedArrays.append((currentArray, negCount))
		if not splittedArrays:
			return 0
		maxLength = 0
		for (splittedArray, negCount) in splittedArrays:
			if negCount % 2 == 0:
				maxLength = max(maxLength, len(splittedArray))
			else:
				removedNums = 0
				i = 0
				while splittedArray[i] > 0:
					removedNums += 1
					i += 1
				maxLength = max(maxLength, len(splittedArray) - removedNums - 1)
				removedNums = 0
				i = len(splittedArray) - 1
				while splittedArray[i] > 0:
					removedNums += 1
					i -= 1
				maxLength = max(maxLength, len(splittedArray) - removedNums - 1)
		return maxLength


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		l = -1
		neg_num = 0
		result = 0
		for i in range(n):
			if nums[i] == 0:
				while neg_num % 2:
					if nums[l + 1] < 0:
						neg_num -= 1
					l += 1
				result = max(result, i - l - 1)
				l = i
				count = 0
			elif nums[i] < 0:
				neg_num += 1
			if neg_num % 2 == 0:
				result = max(result, i - l)
		while neg_num % 2 and l < n - 1:
			if nums[l + 1] < 0:
				neg_num -= 1
			l += 1
		result = max(result, n - 1 - l)
		return result


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if not nums:
			return 0
		size = len(nums)
		if size == 1:
			return 0 if nums[0] < 0 else 1
		start = 0
		end = 0
		longest = 0
		while end < size:
			numNeg = 0
			leftNeg = -1
			rightNeg = -1
			while end < size and (not nums[end] == 0):
				if nums[end] < 0:
					numNeg += 1
					rightNeg = end
					if leftNeg == -1:
						leftNeg = end
				end += 1
			if numNeg % 2 == 0:
				longest = max(longest, end - start)
			else:
				longest = max(longest, end - rightNeg - 1, rightNeg - start, end - leftNeg - 1, leftNeg - start)
			end += 1
			start = end
		return longest


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		(pos, neg) = (-1, n)
		c = 1
		ret = 0
		for (i, j) in enumerate(nums):
			if j == 0:
				(pos, neg) = (i, n)
				c = 1
				continue
			if j > 0:
				pass
			else:
				c *= -1
			if c == 1:
				ret = max(ret, i - pos)
			else:
				ret = max(ret, i - neg)
				neg = min(neg, i)
		return ret


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = [[0] * 2 for _ in range(len(nums))]
		dp[0][0] = nums[0] > 0
		dp[0][1] = nums[0] < 0
		ret = dp[0][0]
		for i in range(1, len(nums)):
			if nums[i] == 0:
				continue
			if nums[i] > 0:
				dp[i][0] = dp[i - 1][0] + 1
				dp[i][1] = 0 if not dp[i - 1][1] else dp[i - 1][1] + 1
			else:
				dp[i][0] = 0 if not dp[i - 1][1] else dp[i - 1][1] + 1
				dp[i][1] = dp[i - 1][0] + 1
			ret = max(ret, dp[i][0])
		return int(ret)


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		l = len(nums)
		pdp = [0] * l
		ndp = [0] * l
		pdp[0] = 1 if nums[0] > 0 else 0
		ndp[0] = 1 if nums[0] < 0 else 0
		b = pdp[0]
		for i in range(1, l):
			n = nums[i]
			if n > 0:
				pdp[i] = max(pdp[i - 1] + 1, 1)
				ndp[i] = ndp[i - 1] + 1 if ndp[i - 1] != 0 else 0
			elif n < 0:
				ndp[i] = max(pdp[i - 1] + 1, 1)
				pdp[i] = ndp[i - 1] + 1 if ndp[i - 1] != 0 else 0
			else:
				pdp[i] = 0
				ndp[i] = 0
			b = max(b, pdp[i])
		return b


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		dp = [[0] * 2 for _ in range(len(nums))]
		if nums[0] < 0:
			dp[0][1] = 1
		if nums[0] > 0:
			dp[0][0] = 1
		res = dp[0][0]
		for (i, num) in enumerate(nums):
			if i and num < 0:
				dp[i][1] = dp[i - 1][0] + 1
				if dp[i - 1][1]:
					dp[i][0] = dp[i - 1][1] + 1
			if i and num > 0:
				dp[i][0] = dp[i - 1][0] + 1
				if dp[i - 1][1]:
					dp[i][1] = dp[i - 1][1] + 1
			res = max(res, dp[i][0])
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		if not nums:
			return 0
		cur_pos_product_len = 1 if nums[0] > 0 else 0
		cur_neg_product_len = 1 if nums[0] < 0 else 0
		max_len = cur_pos_product_len
		for i in range(1, len(nums)):
			if nums[i] > 0:
				cur_pos_product_len += 1
				cur_neg_product_len = cur_neg_product_len + 1 if cur_neg_product_len > 0 else 0
			elif nums[i] < 0:
				temp = cur_pos_product_len
				cur_pos_product_len = cur_neg_product_len + 1 if cur_neg_product_len > 0 else 0
				cur_neg_product_len = temp + 1
			else:
				cur_pos_product_len = 0
				cur_neg_product_len = 0
			max_len = max(max_len, cur_pos_product_len)
		return max_len


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		arrs = [[]]
		for i in nums:
			if i:
				arrs[-1].append(i)
			else:
				arrs.append([])
		ans = 0
		for arr in arrs:
			if not len(arr):
				continue
			negs = 0
			for i in arr:
				if i < 0:
					negs += 1
			if negs % 2:
				p1 = 0
				while arr[p1] > 0:
					p1 += 1
				p2 = len(arr) - 1
				while arr[p2] > 0:
					p2 -= 1
				ans = max(len(arr) - p1 - 1, p2, ans)
			else:
				ans = max(ans, len(arr))
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		pos_length = 0
		neg_length = 0
		max_length = 0
		for num in nums:
			if num > 0:
				pos_length += 1
				if neg_length:
					neg_length += 1
			elif num < 0:
				tmp = pos_length
				if neg_length:
					pos_length = neg_length + 1
				else:
					pos_length = 0
				neg_length = tmp + 1
			else:
				pos_length = 0
				neg_length = 0
			max_length = max(max_length, pos_length)
		max_length = max(max_length, pos_length)
		return max_length


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		n = len(nums)
		dp = [[0, 0] for _ in range(n)]
		for i in range(n):
			if nums[i] == 0:
				dp[i] = [0, 0]
			elif i == 0 or nums[i - 1] == 0:
				if nums[i] > 0:
					dp[i][0] = 1
				else:
					dp[i][1] = 1
			elif nums[i] > 0:
				dp[i][0] = dp[i - 1][0] + 1
				if dp[i - 1][1] > 0:
					dp[i][1] = dp[i - 1][1] + 1
			else:
				if dp[i - 1][1] > 0:
					dp[i][0] = dp[i - 1][1] + 1
				dp[i][1] = dp[i - 1][0] + 1
		return max((dp[i][0] for i in range(n)))


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		nums.append(0)
		left = 0
		n = len(nums)
		first_neg = n
		last_neg = 0
		ct_neg = 0
		ans = 0
		for right in range(n):
			if nums[right] < 0:
				first_neg = min(first_neg, right)
				last_neg = max(last_neg, right)
				ct_neg += 1
			elif nums[right] == 0:
				if left < right:
					if ct_neg & 1 == 0:
						ans = max(ans, right - left)
					else:
						print(left, right, first_neg, last_neg)
						ans = max(ans, right - first_neg - 1)
						ans = max(ans, last_neg - left)
				left = right + 1
				first_neg = n
				last_neg = 0
				ct_neg = 0
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		res = 0
		for (is_pos, group) in itertools.groupby(nums, key=bool):
			if is_pos:
				subgroup = list(group)
				num_negs = 0
				first = last = None
				for (i, n) in enumerate(subgroup):
					if n < 0:
						num_negs += 1
						if first is None:
							first = i
						last = i
				if num_negs % 2 == 0:
					res = max(res, len(subgroup))
				else:
					res = max(res, first, len(subgroup) - 1 - first)
					res = max(res, last, len(subgroup) - 1 - last)
		return res


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		ans = 0
		neg_pos = None
		neg_count = 0
		left = -1
		for (i, n) in enumerate(nums):
			if n == 0:
				neg_pos = None
				neg_count = 0
				left = i
				continue
			elif n > 0:
				if neg_count % 2 == 0:
					ans = max(ans, i - left)
				else:
					ans = max(ans, i - neg_pos)
			elif n < 0:
				neg_count += 1
				if neg_pos is None:
					neg_pos = i
				if neg_count % 2 == 0:
					ans = max(ans, i - left)
				else:
					ans = max(ans, i - neg_pos)
		return ans

	def getMaxLen1(self, nums: List[int]) -> int:
		ans = 0
		dq = []
		left = -1
		for (i, n) in enumerate(nums):
			if n == 0:
				dq.clear()
				left = i
				continue
			elif n > 0:
				if len(dq) % 2 == 0:
					ans = max(ans, i - left)
				else:
					ans = max(ans, i - dq[0])
			elif n < 0:
				dq.append(i)
				if len(dq) % 2 == 0:
					ans = max(ans, i - left)
				else:
					ans = max(ans, i - dq[0])
		return ans


class Solution:

	def getMaxLen(self, nums: List[int]) -> int:
		f_pos = 0
		f_neg = 0
		max_pos = 0
		for i in range(len(nums)):
			if nums[i] == 0:
				(f_pos, f_neg) = (0, 0)
			elif nums[i] > 0:
				f_pos += 1
				if f_neg > 0:
					f_neg += 1
			else:
				tmp = f_pos
				if f_neg > 0:
					f_pos = f_neg + 1
				else:
					f_pos = 0
				f_neg = tmp + 1
			print((i, f_pos, f_neg))
			max_pos = max(max_pos, f_pos)
		return max_pos


from typing import List

class Solution:

	def getMaxLen(self, nums: List[int]) -> int:

		def aux(i, j):
			negs = 0
			for v in nums[i:j + 1]:
				if v < 0:
					negs += 1
			if negs % 2 == 0:
				return j - i + 1
			l = i
			while nums[l] > 0:
				l += 1
			l = j - l
			r = j
			while nums[r] > 0:
				r -= 1
			r = r - i
			return max(l, r)
		start = 0
		maxm = 0
		for end in range(len(nums)):
			if nums[end] == 0:
				maxm = max(maxm, aux(start, end - 1))
				start = end + 1
			elif nums[end] > 0:
				maxm = max(maxm, 1)
		if start != len(nums) - 1:
			maxm = max(maxm, aux(start, len(nums) - 1))
		return maxm


import bisect

class Solution:
	ans = [0 for i in range(100001)]

	def getMaxLen(self, nums: List[int]) -> int:

		def solve(arr):
			(s1, s2) = (set(), set())
			s1.add(-1)
			ret = 0
			cnt = 0
			n = len(arr)
			for (i, c) in enumerate(arr):
				cnt += 0 if c > 0 else 1
				if cnt % 2 == 0:
					s1.add(i)
				else:
					s2.add(i)
			if s1:
				ret = max(s1) - min(s1)
			if s2:
				ret = max(max(s2) - min(s2), ret)
			return ret
		ans = 0
		l = 0
		for (i, c) in enumerate(nums):
			if c == 0:
				ans = max(ans, solve(nums[l:i]))
				l = i + 1
		ans = max(ans, solve(nums[l:]))
		return ans