#CF2266D. Falling Concrete

Falling Concrete

Problem Description

Vihaan is repairing a road consisting of $n$ sections. The height of the $i$-th section is $a_i$.

He has a forklift which can move road sections. In one operation, Vihaan chooses two indices $i$ and $j$ ($1 \le i \lt j \le n$), picks up the $j$-th section, and moves it backwards to position $i$.

As the section is carried backwards, one unit of concrete falls from it onto each section it passes over. Then, the carried section is inserted at position $i$.

More formally, the subarray $$ [a_i,a_{i+1},\ldots,a_{j-1},a_j] $$ is replaced with $$ [a_j-(j-i),a_i+1,a_{i+1}+1,\ldots,a_{j-1}+1]. $$

A part of the road is called flat if it is a contiguous segment of sections with equal heights.

Vihaan may perform any number of operations, possibly zero.

Find the maximum possible length of a flat part of the road.

Input Format

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of sections of the road.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ (${\color{red}n} \le a_i \le 10^9$) — the initial heights of the sections.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

It can be shown that under the given constraints, the height of every section remains positive after any sequence of operations.

Output Format

For each test case, print a single integer — the maximum possible length of a flat part of the road.

Examples

8
5
5 5 5 9 8
6
6 6 6 6 6 6
5
5 6 7 8 9
5
9 7 12 10 12
4
4 7 5 8
7
14 9 14 12 8 11 12
5
1000000000 1000000000 1000000000 1000000000 1000000000
8
8 8 12 8 14 10 15 13
4
6
1
5
4
2
5
6

Note

In the first test case, Vihaan can move the section at position $4$ to position $1$:

$$ [{\color{red}5},{\color{red}5},{\color{red}5},{\color{red}9},8] \rightarrow [{\color{red}6},{\color{red}6},{\color{red}6},{\color{red}6},8]. $$

Thus, a flat part of length $4$ can be created.

In the fourth test case, Vihaan can perform the following operations:

  1. Move the section at position $3$ to position $1$:

    $$ [{\color{red}9},{\color{red}7},{\color{red}1}{\color{red}2},10,12] \rightarrow [{\color{red}1}{\color{red}0},{\color{red}1}{\color{red}0},{\color{red}8},10,12]. $$

  2. Move the section at position $4$ to position $3$:

    $$ [10,10,{\color{red}8},{\color{red}1}{\color{red}0},12] \rightarrow [10,10,{\color{red}9},{\color{red}9},12]. $$

  3. Move the section at position $5$ to position $3$:

    $$ [10,10,{\color{red}9},{\color{red}9},{\color{red}1}{\color{red}2}] \rightarrow [10,10,{\color{red}1}{\color{red}0},{\color{red}1}{\color{red}0},{\color{red}1}{\color{red}0}]. $$

Thus, the entire road can be made flat.

In the fifth test case, Vihaan can first move the section at position $2$ to position $1$:

$$ [{\color{red}4},{\color{red}7},5,8] \rightarrow [{\color{red}6},{\color{red}5},5,8]. $$

Then, he can move the section at position $4$ to position $2$:

$$ [6,{\color{red}5},{\color{red}5},{\color{red}8}] \rightarrow [6,{\color{red}6},{\color{red}6},{\color{red}6}]. $$

Thus, the entire road can be made flat.

Source

Imported from Codeforces — Codeforces Round 1122 (Div. 3).