← 返回题目列表

Codeforces · 1872/G

G. 更换为产品

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

给定一个包含 $$$n$$$ 正整数的数组 $$$a$$$。您需要执行以下操作一次:

- 选择 $$$2$$$ 整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 并将子数组 $$$a[l \ldots r]$$$ 替换为单个元素:子数组 $$$(a_l \cdot \ldots \cdot a_r)$$$ 中所有元素的乘积。

例如,如果对数组 $$$[5, 4, 3, 2, 1]$$$ 进行参数 $$$l = 2, r = 4$$$ 的运算,则数组将变为 $$$[5, 24, 1]$$$。

您的任务是在应用此操作后最大化数组的总和。找到应用此操作的最佳子数组。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个数字 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

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

输出

对于每个测试用例,输出 $$$2$$$ 整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) — 要替换为乘积的子数组的边界。

如果有多个解,则输出其中任意一个。

示例

输入 #1

9
4
1 3 1 3
4
1 1 2 3
5
1 1 1 1 1
5
10 1 10 1 10
1
1
2
2 2
3
2 1 2
4
2 1 1 3
6
2 1 2 1 1 3

输出 #1

2 4
3 4
1 1
1 5
1 1
1 2
2 2
4 4
1 6

注意

在第一个测试用例中,应用参数 $$$l = 2, r = 4$$$ 的运算后,数组 $$$[1, 3, 1, 3]$$$ 变成 $$$[1, 9]$$$,总和等于 $$$10$$$。很容易看出,通过用产品替换任何其他部分,总和将小于 $$$10$$$。

在第二个测试用例中,应用参数 $$$l = 3, r = 4$$$ 的运算后,数组 $$$[1, 1, 2, 3]$$$ 变成 $$$[1, 1, 6]$$$,总和等于 $$$8$$$。很容易看出,通过用产品替换任何其他部分,总和将小于 $$$8$$$。

在第三个测试用例中,最好选择 $$$l = r$$$ 的任何操作,然后数组的总和将保持 $$$5$$$,并且当应用任何其他操作时,数组的总和将减少。