CF2266D Falling Concrete

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.

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.

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

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