题目描述

给定一个包含 $n$ 个整数的数组 $a$ ，对于每个 $i(1≤i≤n)$ ，以下不等式成立： $-2≤a_i≤2$ 。

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

你需要回答以下问题：应该从数组开头删除多少个元素，以及应该从数组末尾删除多少个元素，使结果成为一个元素乘积最大的数组。如果有多种方法可以得到乘积最大的数组，则允许输出任意一种。

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

输入格式

输入数据的第一行包含一个整数 $t(1≤t≤10^4)$ ——测试中测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例描述的第一行包含一个整数 $n(1≤n≤2⋅10^5)$ ——数组 $a$ 的长度。

接下来一行包含 $n$ 个整数 $a_1,a_2,…,a_n(|a_i|≤2)$ ——数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $2⋅10^5$ 。

对于每个测试用例，请输出两个非负整数 $x$ 和 $y(0≤x+y≤n)$ ，以便在从数组开头删除 $x$ 个元素和从数组末尾删除 $y$ 个元素后，数组数字的乘积（乘法）最大化。

如果有多种方法可以获得最大乘积，则允许任意输出其中任意一种。空数组的数字积为 $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

在第一个案例中，最大乘积的最大值为 $2$ 。因此，我们可以删除前三个元素（得到数组 $[2]$ ），或者删除最后两个和第一个元素（也得到数组 $[2]$ ），或者只删除最后两个元素（得到数组 $[1,2]$ ）。因此，在第一个案例中，答案是 3 0 或 1 2 或 0 2。

在第二个案例中，乘积的最大值是 $1$ 。然后我们可以从数组中删除所有元素，因为空数组的乘积值为 $1$ 。因此，答案是 3 0，但是还有其他可能的答案。

在第三个案例中，我们可以删除数组的前两个元素。然后我们得到数组： $[−2,2,−1]$ 。得到的数组元素的乘积是 $(−2)⋅2⋅(−1)=4$ 。这个值是可以获得的最大值。因此，对于这种情况，答案是 2 0。