# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

An integer sequence `$b_1, b_2, \ldots, b_m$`

is a pyramid if it satisfies the following conditions:

`$m$`

is odd.- For each valid
`$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:

- Select an element, and decrease it by exactly
`$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 |

62% Solution Ratio

Ashiqur.141492Earliest,

TurinhstuFastest, 0.1s

TurinhstuLightest, 24 MB

ash_98Shortest, 852B

Login to submit