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

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

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

输入 #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