Practice on Toph

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

Subarray Pyramid

By ovis96 · Limits 2.5s, 1.0 GB

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

Input

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

Output

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.

Sample

InputOutput
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

Statistics

72% Solution Ratio

Ashiqur.141492Earliest, Dec '20

TurinhstuFastest, 0.1s

TurinhstuLightest, 24 MB

nihalshahriaShortest, 763B

Submit

 Replay of Virtual Techfest 2020 Regional Programming Contest Dec '20 Virtual Techfest 2020 Regional Programming Contest Dec '20 