You are given an array $a$ consisting of $n$ integers. For each $i$ ($1 \le i \le n$) the following inequality is true: $-2 \le a_i \le 2$.

You can remove any number (possibly $0$) of elements from the beginning of the array and any number (possibly $0$) of elements from the end of the array. You are allowed to delete the whole array.

You need to answer the question: how many elements should be removed from the beginning of the array, and how many elements should be removed from the end of the array, so that the result will be an array whose product (multiplication) of elements is maximal. If there is more than one way to get an array with the maximum product of elements on it, you are allowed to output any of them.

The product of elements of an empty array (array of length $0$) should be assumed to be $1$.


-----Input-----

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

Then the descriptions of the input test cases follow.

The first line of each test case description contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) —the length of array $a$.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($|a_i| \le 2$) — elements of array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output two non-negative numbers $x$ and $y$ ($0 \le x + y \le n$) — such that the product (multiplication) of the array numbers, after removing $x$ elements from the beginning and $y$ elements from the end, is maximal.

If there is more than one way to get the maximal product, it is allowed to output any of them. Consider the product of numbers on empty array to be $1$.


-----Examples-----

Input
5
4
1 2 -1 2
3
1 1 -2
5
2 0 -2 2 -1
3
-2 -1 -1
3
-1 -2 -2
Output
0 2
3 0
2 0
0 1
1 0


-----Note-----

In the first case, the maximal value of the product is $2$. Thus, we can either delete the first three elements (obtain array $[2]$), or the last two and one first element (also obtain array $[2]$), or the last two elements (obtain array $[1, 2]$). Thus, in the first case, the answers fit: "3 0", or "1 2", or "0 2".

In the second case, the maximum value of the product is $1$. Then we can remove all elements from the array because the value of the product on the empty array will be $1$. So the answer is "3 0", but there are other possible answers.

In the third case, we can remove the first two elements of the array. Then we get the array: $[-2, 2, -1]$. The product of the elements of the resulting array is $(-2) \cdot 2 \cdot (-1) = 4$. This value is the maximum possible value that can be obtained. Thus, for this case the answer is: "2 0".

Difficulty: MEDIUM_HARD
Tags: Mathematics

Amortized analysis

Implementation

Complete search
Skill types: Amortized analysis

Complete search

Starter code:

Solutions:
from math import sqrt, ceil
import os
import sys
from collections import defaultdict, deque
from io import BytesIO, IOBase
from collections import Counter
from functools import lru_cache
from collections import deque

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		(l_ind, r_ind) = (0, n)
		res = 0
		pl = 0
		pr = 0
		nl = None
		nv = None
		temp = 1
		c = 0
		for (i, el) in enumerate(arr):
			if el > 0:
				temp *= 1
			elif el < 0:
				temp *= -1
			else:
				temp = 0
			if abs(el) == 2:
				c += 1
			if temp > 0:
				if c > res:
					res = c
					l_ind = pl
					r_ind = i
			elif temp < 0:
				if nv == None:
					nl = i
					nv = c
				elif c - nv > res:
					res = c - nv
					l_ind = nl + 1
					r_ind = i
			else:
				pl = i + 1
				pr = 0
				nl = None
				nv = None
				temp = 1
				c = 0
		(a, b, v) = (l_ind, r_ind, res)
		if v == 0:
			print(n, 0)
		else:
			print(a, n - b - 1)
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		(l_ind, r_ind) = (0, n)
		res = 0
		pl = 0
		pr = 0
		nl = None
		nv = None
		temp = 1
		c = 0
		for (i, el) in enumerate(arr):
			if el > 0:
				temp *= 1
			elif el < 0:
				temp *= -1
			else:
				temp = 0
			if abs(el) == 2:
				c += 1
			if temp > 0:
				if c > res:
					res = c
					l_ind = pl
					r_ind = i
			elif temp < 0:
				if nv == None:
					nl = i
					nv = c
				elif c - nv > res:
					res = c - nv
					l_ind = nl + 1
					r_ind = i
			else:
				pl = i + 1
				pr = 0
				nl = None
				nv = None
				temp = 1
				c = 0
		(a, b, v) = (l_ind, r_ind, res)
		if v == 0:
			print(n, 0)
		else:
			print(a, n - b - 1)
main()


import sys
import math

def cal(a):
	count = 0
	for x in a:
		if x < 0:
			count = count + 1
	if count % 2 == 0:
		sum = 0
		for x in a:
			if abs(x) > 1:
				sum += 1
		return [sum, 0, 0]
	neg = []
	for i in range(len(a)):
		if a[i] < 0:
			neg.append(i)
	x = 0
	for i in range(neg[0] + 1, len(a)):
		x += abs(a[i]) > 1
	y = 0
	for i in range(0, neg[-1]):
		y += abs(a[i]) > 1
	if x > y:
		return [x, neg[0] + 1, 0]
	else:
		return [y, 0, len(a) - neg[-1]]
ttime = int(input())
for ccount in range(ttime):
	n = int(input())
	a = list(map(int, input().split()))
	ans = (0, 0, len(a))
	prev = []
	for i in range(len(a)):
		if a[i] == 0:
			temp = cal(prev)
			temp[1] = temp[1] + i - len(prev)
			temp[2] = temp[2] + len(a) - i
			if ans[0] < temp[0]:
				ans = temp
			prev = []
		else:
			prev.append(a[i])
	if len(prev) > 0:
		temp = cal(prev)
		temp[1] = temp[1] + len(a) - len(prev)
		if ans[0] < temp[0]:
			ans = temp
	print(ans[1], ans[2])


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	ans = 0
	(ansl, ansr) = (n, 0)
	l = -1
	for i in range(n + 1):
		if i == n or nums[i] == 0:
			count = 0
			left = -1
			right = -1
			neg = 1
			zr = 0
			zl = 0
			for j in range(l + 1, i):
				if nums[j] < 0:
					neg *= -1
					right = j
					zr = 0
				if abs(nums[j]) == 2:
					count += 1
					zr += 1
					if left == -1:
						zl += 1
				if nums[j] < 0 and left == -1:
					left = j
			if neg == -1:
				if count - zl > count - zr:
					right = i
					count -= zl
				else:
					left = l
					count -= zr
			else:
				left = l
				right = i
			if ans < count:
				ans = count
				ansl = left + 1
				ansr = n - right
			l = i
	print(ansl, ansr)


def count(nums):
	total = {-2: 0, -1: 0, 1: 0, 2: 0}
	for i in nums:
		total[i] += 1
	return total

def solution():
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = 0
	(x, y) = (n, 0)
	zero_pos = [-1] + [i for i in range(n) if a[i] == 0] + [n]
	for i in range(len(zero_pos) - 1):
		(l, r) = (zero_pos[i] + 1, zero_pos[i + 1] - 1)
		c = count(a[l:r + 1])
		if (c[-1] + c[-2]) % 2 == 0 and c[2] + c[-2] > ans:
			ans = c[2] + c[-2]
			(x, y) = (l, n - r - 1)
		elif (c[-1] + c[-2]) % 2 != 0:
			(leftpos, rightpos) = (l, r)
			while a[leftpos] > 0:
				leftpos += 1
			while a[rightpos] > 0:
				rightpos -= 1
			c = count(a[l:rightpos])
			if c[2] + c[-2] > ans:
				ans = c[2] + c[-2]
				(x, y) = (l, n - rightpos)
			c = count(a[leftpos + 1:r + 1])
			if c[2] + c[-2] > ans:
				ans = c[2] + c[-2]
				(x, y) = (leftpos + 1, n - r - 1)
	print(x, y)
t = int(input())
for _ in range(t):
	solution()


tests = int(input())
for _ in range(tests):
	num_len = int(input())
	n = num_len
	all_num = input()
	a = [int(i) for i in all_num.split(' ')]
	a = [1] + a + [0]
	m = 0
	lef = 0
	rig = num_len
	num_len = len(a)
	op = [0] * num_len
	ex = [0] * num_len
	j = 0
	l = 0
	for i in range(1, num_len):
		if a[i] < 0:
			op[i] = op[i - 1] + 1
		else:
			op[i] = op[i - 1]
		if a[i] == 2 or a[i] == -2:
			ex[i] = ex[i - 1] + 1
		else:
			ex[i] = ex[i - 1]
		if a[i] == 0:
			for j in range(l + 1, i):
				if (op[j] - op[l]) % 2 == 0 and ex[j] - ex[l] > m:
					lef = l
					rig = n - j
					m = ex[j] - ex[l]
				if (op[i - 1] - op[j - 1]) % 2 == 0 and ex[i - 1] - ex[j - 1] > m:
					lef = j - 1
					rig = n - i + 1
					m = ex[i - 1] - ex[j - 1]
			l = i
	print('{} {}'.format(lef, rig))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	best = (1, 0, n, 0)
	best_pow_neg = (1, 0, 0)
	best_pow_pos = (1, 0, 0)
	prefix_pow = 0
	prefix_sign = 1
	for i in range(n):
		if a[i] == 0:
			best_pow_neg = (1, 0, i + 1)
			best_pow_pos = (1, 0, i + 1)
			prefix_pow = 0
			prefix_sign = 1
			continue
		prefix_pow += abs(a[i]) == 2
		prefix_sign *= a[i] // abs(a[i])
		if prefix_sign == -1:
			cur = (prefix_sign * best_pow_neg[0], prefix_pow - best_pow_neg[1], best_pow_neg[2], n - i - 1)
		else:
			cur = (prefix_sign * best_pow_pos[0], prefix_pow - best_pow_pos[1], best_pow_pos[2], n - i - 1)
		best = max(best, cur)
		if prefix_sign == 1:
			best_pow_pos = min(best_pow_pos, (prefix_sign, prefix_pow, i + 1))
		if best_pow_neg[0] == 1 or prefix_pow < best_pow_neg[1]:
			best_pow_neg = (prefix_sign, prefix_pow, i + 1)
	print(best[2], best[3])


t = int(input())
for _ in range(t):
	n = int(input())
	numbers = [int(num) for num in input().split()]
	max_pow_2 = 0
	remove_from_start = n
	remove_from_end = 0
	idx = 0
	j = 0
	pow_2 = 0
	sign = True
	while idx < n:
		if numbers[idx] == 0:
			idx += 1
			j = idx
			pow_2 = 0
			sign = True
			continue
		if idx > 0 and numbers[idx - 1] != 0:
			if numbers[idx - 1] < 0:
				sign = not sign
			if abs(numbers[idx - 1]) == 2:
				pow_2 -= 1
			if sign and pow_2 > max_pow_2:
				max_pow_2 = pow_2
				remove_from_start = idx
				remove_from_end = n - j
		while j < n and numbers[j] != 0:
			if numbers[j] < 0:
				sign = not sign
			if abs(numbers[j]) == 2:
				pow_2 += 1
			if sign and pow_2 > max_pow_2:
				max_pow_2 = pow_2
				remove_from_start = idx
				remove_from_end = n - j - 1
			j += 1
		idx += 1
	print(remove_from_start, remove_from_end)


from collections import defaultdict
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.append(0)
	solve_for = []
	ans = 0
	begin = 0
	end = 0
	for (idx, i) in enumerate(arr):
		if i != 0:
			if len(solve_for) == 0:
				begin = idx
			solve_for.append(i)
			end = idx
		else:
			solve_for.clear()
			tmp_ans = 1
			twos = 0
			negs = 0
			for i in range(begin, end + 1):
				if abs(arr[i]) == 2:
					twos += 1
				if arr[i] < 0:
					negs += 1
				if negs % 2 == 0:
					if twos > ans:
						fin_beg = begin
						fin_end = i
						ans = twos
			twos = 0
			negs = 0
			for i in range(end, begin - 1, -1):
				if abs(arr[i]) == 2:
					twos += 1
				if arr[i] < 0:
					negs += 1
				if negs % 2 == 0:
					if twos > ans:
						fin_beg = i
						fin_end = end
						ans = twos
	if ans == 0:
		print(0, n)
	else:
		print(fin_beg, n - (fin_end + 1))


t = int(input())
for i in range(t):
	_ = int(input())
	nums = list(map(int, input().split()))
	start = 0
	end = 0
	count_2 = 0
	neg = 1
	max_prod = 0
	max_range = [0, 0]
	while start <= end and start < len(nums):
		if end == len(nums) or nums[end] == 0:
			if start == end:
				count_2 = 0
				start = end = end + 1
				continue
			count_2 -= abs(nums[start]) // 2
			neg *= nums[start] // abs(nums[start])
			start += 1
			if neg * count_2 > max_prod:
				max_prod = count_2
				max_range = [start, end]
		else:
			count_2 += abs(nums[end]) // 2
			neg *= nums[end] // abs(nums[end])
			end += 1
			if neg * count_2 > max_prod:
				max_prod = count_2
				max_range = [start, end]
	print(max_range[0], len(nums) - max_range[1])