CF1660D.Maximum Product Strikes Back

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$.

给你一个由 $n$ 个整数组成的数组 $a$。对每个 $i$（$1 \le i \le n$），均满足不等式：$-2 \le a_i \le 2$。

你可以从数组开头移除任意数量（可能为 $0$）的元素，也可以从数组末尾移除任意数量（可能为 $0$）的元素。你甚至可以将整个数组全部删除。

你需要回答以下问题：应从数组开头移除多少个元素、从数组末尾移除多少个元素，才能使剩余数组中所有元素的乘积（即各元素相乘的结果）达到最大？如果存在多种方式能得到最大乘积的数组，你可以输出其中任意一种方案。

空数组（长度为 $0$ 的数组）的元素乘积定义为 $1$。

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$.

输入数据的第一行包含一个整数 $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$。

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$.

对于每个测试用例，输出两个非负整数 $x$ 和 $y$（满足 $0 \le x + y \le n$），使得在从数组开头移除 $x$ 个元素、从数组末尾移除 $y$ 个元素后，剩余数组中所有数字的乘积（即乘法结果）最大。

若存在多种方案可得到最大乘积，则输出其中任意一种即可。规定空数组的乘积为 $1$。

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".

第一种情况中，乘积的最大值为 $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”。