Replace With Product
Contest: Codeforces Round 895 (Div. 3)
Difficulty rating: 2000
Tags: brute force, greedy, math

Given an array $$$a$$$ of $$$n$$$ positive integers. You need to perform the following operation exactly once:

- Choose $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) and replace the subarray $$$a[l \ldots r]$$$ with the single element: the product of all elements in the subarray $$$(a_l \cdot \ldots \cdot a_r)$$$.

For example, if an operation with parameters $$$l = 2, r = 4$$$ is applied to the array $$$[5, 4, 3, 2, 1]$$$, the array will turn into $$$[5, 24, 1]$$$.

Your task is to maximize the sum of the array after applying this operation. Find the optimal subarray to apply this operation.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. This is followed by the description of the test cases.

The first line of each test case contains a single number $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of the values of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the boundaries of the subarray to be replaced with the product.

If there are multiple solutions, output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, after applying the operation with parameters $$$l = 2, r = 4$$$, the array $$$[1, 3, 1, 3]$$$ turns into $$$[1, 9]$$$, with a sum equal to $$$10$$$. It is easy to see that by replacing any other segment with a product, the sum will be less than $$$10$$$.

In the second test case, after applying the operation with parameters $$$l = 3, r = 4$$$, the array $$$[1, 1, 2, 3]$$$ turns into $$$[1, 1, 6]$$$, with a sum equal to $$$8$$$. It is easy to see that by replacing any other segment with a product, the sum will be less than $$$8$$$.

In the third test case, it will be optimal to choose any operation with $$$l = r$$$, then the sum of the array will remain $$$5$$$, and when applying any other operation, the sum of the array will decrease.

Example input:
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

Example output:
2 4
3 4
1 1
1 5
1 1
1 2
2 2
4 4
1 6

Editorial:
Key observation: if the product of all elements in the array is sufficiently large, it is always optimal to perform the operation on the entire array, except for a possible prefix/suffix consisting of ones.
You can estimate sufficiently large, for example, with the number $$$2^{60}$$$ (in reality, $$$2 \cdot n$$$ will be sufficient). There won't be a proof, but that's how it is.
Now the problem reduces to the case where the product of the array is not greater than $$$2^{60}$$$. This means that the number of array elements that are $$$> 1$$$ is at most $$$60$$$.
Notice that in an optimal segment, there won't be a situation where the left/right element is equal to $$$1$$$, because then we can move that boundary and the sum will increase by $$$1$$$.
Therefore, both the start and end of the segment must be in non-ones elements. This means that there are at most $$$60^2$$$ interesting segment options.
We can explicitly iterate through all of them and choose the best one. Use prefix products and sums to quickly estimate the value of a specific segment.