← 返回题目列表

Codeforces · 1660/D

D. 最大产品的反击

中文机器翻译题面 查看原题

给定一个由 $$$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”。