#CF2266D. Falling Concrete

Falling Concrete

Problem Description

Vihaan 正在维修一条由 nn 个路段组成的道路。第 ii 个路段的高度为 aia_i。

他有一辆叉车,可以移动路段。在一次操作中,Vihaan 选择两个下标 ii 和 jj(1≤i<j≤n1 \le i < j \le n),将第 jj 个路段抬起,并向后移动到位置 ii。

当该路段被向后搬运时,每经过一个路段,就会有一单位混凝土从它上面掉落到所经过的路段上。然后,被搬运的路段插入到位置 ii。

更形式化地说,子数组 $$ [a_i,a_{i+1},\ldots,a_{j-1},a_j] $$ 被替换为 $$ [a_j-(j-i),a_i+1,a_{i+1}+1,\ldots,a_{j-1}+1]. $$

如果道路的一部分是由高度相同的连续路段组成的,则称该部分为平坦的。

Vihaan 可以执行任意次操作(包括零次)。

求道路平坦部分的最大可能长度。

Input Format

第一行包含一个整数 tt(1≤t≤1041 \le t \le 10^4)— 测试用例的数量。

每个测试用例的第一行包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)— 道路的路段数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(n≤ai≤109{\color{red}n} \le a_i \le 10^9)— 路段的初始高度。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。

可以证明,在给定约束下,任意操作序列后每个路段的高度始终保持为正。

Output Format

对于每个测试用例,输出一个整数 — 道路平坦部分的最大可能长度。

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

在第一个测试用例中,Vihaan 可以将位置 44 的路段移动到位置 11:

$$[{\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].$$

因此,可以创建一个长度为 44 的平坦部分。

在第四个测试用例中,Vihaan 可以执行以下操作:

  1. 将位置 33 的路段移动到位置 11:$$[{\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. 将位置 44 的路段移动到位置 33:$$[10,10,{\color{red}8},{\color{red}1}{\color{red}0},12] \rightarrow [10,10,{\color{red}9},{\color{red}9},12].$$
  3. 将位置 55 的路段移动到位置 33:$$[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}].$$

因此,整条道路可以变为平坦的。

在第五个测试用例中,Vihaan 可以首先将位置 22 的路段移动到位置 11:

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

然后,他可以将位置 44 的路段移动到位置 22:

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

因此,整条道路可以变为平坦的。

Source

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