An integer sequence $b_1, b_2, \ldots, b_m$
is a pyramid if it satisfies the following conditions:
$m$
is odd.$i$
, $b_i = min(i, m - i + 1)$
.For example, $[1, 2, 3, 4, 3, 2, 1]$
is a pyramid, but $[1, 2, 3, 3, 2, 1]$
and $[1, 3, 2]$
are not.
An integer sequence $c_1, c_2, \ldots, c_k$
is good if it is possible to make it a pyramid by performing the following operation any number of times:
$1$
. Formally, select a valid index $i$
, and then, assign $c_i := c_i - 1$
.The cost of a good sequence is the minimum number of times you have to perform the above operation to make it good.
You are given an integer sequence $a_1, a_2, \ldots a_n$
. You have to find the maximum length of a subarray which is good and among all such subarrays, you have to find the one with the minimum cost.
The subarray of an array $a$
with length $n$
is a contiguous part of the array, i. e. the sequence $𝑎_𝑖,𝑎_{𝑖+1},…,𝑎_𝑗$
for some $1 \le i \le j \le n$
.
The first line of the input contains a single integer $t(1 \le t \le 10)$
denoting the number of test cases. The description of $t$
test cases follows.
The first line of each test case contains a single integer $n(1 \le n \le 2 \cdot 10^6)$
.
The second line contains $n$
space-separated integers $a_1, a_2, \ldots, a_n( 1 \le a_i \le 2 \cdot 10^6)$
.
The sum of $n$
over all test cases does not exceed $2 \cdot 10^6$
.
For each test case, print two space-separated integers — the maximum length of a good subarray and the minimum cost of all good subarrays with the maximum length.
Input | Output |
---|---|
4 5 1 1 5 2 3 4 1 4 2 1 3 1 2 1 10 1 4 4 2 3 5 6 4 2 1 | 3 4 3 3 3 0 7 7 |