给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。对于每个 $$$i$$$ ($$$1 \le i \le n$$$),以下不等式成立:$$$-2 \le a_i \le 2$$$。
您可以从数组开头删除任意数量(可能是 $$$0$$$)的元素,以及从数组末尾删除任意数量(可能是 $$$0$$$)的元素。您可以删除整个数组。
你需要回答这个问题:应该从数组的开头删除多少个元素,从数组的末尾删除多少个元素,这样结果将是一个元素的乘积(乘法)最大的数组。如果有多种方法可以获取具有最大元素乘积的数组,则允许输出其中任何一个。
空数组(长度为 $$$0$$$ 的数组)元素的乘积应假定为 $$$1$$$。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) – 测试中的测试用例数量。
然后是输入测试用例的描述。
每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$|a_i| \le 2$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出两个非负数 $$$x$$$ 和 $$$y$$$ ($$$0 \le x + y \le n$$$) - 使得在从开头删除 $$$x$$$ 元素和从末尾删除 $$$y$$$ 元素后,数组数字的乘积(乘法)最大。
如果获得最大乘积的方法有多种,则允许输出其中任何一种。考虑空数组上数字的乘积为 $$$1$$$。
示例
输入 #1
5 4 1 2 -1 2 3 1 1 -2 5 2 0 -2 2 -1 3 -2 -1 -1 3 -1 -2 -2
输出 #1
0 2 3 0 2 0 0 1 1 0
注意
在第一种情况下,产品的最大值为$$$2$$$。因此,我们可以删除前三个元素(获取数组$$$[2]$$$),或者删除最后两个和一个第一个元素(也获取数组$$$[2]$$$),或者删除最后两个元素(获取数组$$$[1, 2]$$$)。因此,在第一种情况下,答案适合:“3 0”,或“1 2”,或“0 2”。
在第二种情况下,产品的最大值为$$$1$$$。然后我们可以从数组中删除所有元素,因为空数组上的乘积的值为 $$$1$$$。所以答案是“3 0”,但还有其他可能的答案。
在第三种情况下,我们可以删除数组的前两个元素。然后我们得到数组:$$$[-2, 2, -1]$$$。结果数组元素的乘积为 $$$(-2) \cdot 2 \cdot (-1) = 4$$$。该值是可以获得的最大可能值。因此,对于这种情况,答案是:“2 0”。