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 b1,b2,,bmb_1, b_2, \ldots, b_m is a pyramid if it satisfies the following conditions:

  • mm is odd.
  • For each valid ii, bi=min(i,mi+1)b_i = min(i, m - i + 1).

For example, [1,2,3,4,3,2,1][1, 2, 3, 4, 3, 2, 1] is a pyramid, but [1,2,3,3,2,1][1, 2, 3, 3, 2, 1] and [1,3,2][1, 3, 2] are not.

An integer sequence c1,c2,,ckc_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 11. Formally, select a valid index ii, and then, assign ci:=ci1c_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 a1,a2,ana_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 aa with length $n$ is a contiguous part of the array, i. e. the sequence 𝑎𝑖,𝑎𝑖+1,,𝑎𝑗𝑎_𝑖,𝑎_{𝑖+1},…,𝑎_𝑗 for some 1ijn1 \le i \le j \le n.

Input

The first line of the input contains a single integer t(1t10)t(1 \le t \le 10) denoting the number of test cases. The description of tt test cases follows.

The first line of each test case contains a single integer n(1n2106)n(1 \le n \le 2 \cdot 10^6).

The second line contains nn space-separated integers a1,a2,,an(1ai2106)a_1, a_2, \ldots, a_n( 1 \le a_i \le 2 \cdot 10^6).

The sum of nn over all test cases does not exceed 21062 \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

    Discussion

    Statistics


    72% Solution Ratio

    Ashiqur.141492Earliest, 9M ago

    TurinhstuFastest, 0.1s

    TurinhstuLightest, 24 MB

    nihalshahriaShortest, 763B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.