#CF2266D. Falling Concrete
Falling Concrete
Problem Description
Vihaan 正在维修一条由 个路段组成的道路。第 个路段的高度为 。
他有一辆叉车,可以移动路段。在一次操作中,Vihaan 选择两个下标 和 (),将第 个路段抬起,并向后移动到位置 。
当该路段被向后搬运时,每经过一个路段,就会有一单位混凝土从它上面掉落到所经过的路段上。然后,被搬运的路段插入到位置 。
更形式化地说,子数组 $$ [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
第一行包含一个整数 ()— 测试用例的数量。
每个测试用例的第一行包含一个整数 ()— 道路的路段数。
第二行包含 个整数 ()— 路段的初始高度。
保证所有测试用例的 之和不超过 。
可以证明,在给定约束下,任意操作序列后每个路段的高度始终保持为正。
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 可以将位置 的路段移动到位置 :
$$[{\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].$$因此,可以创建一个长度为 的平坦部分。
在第四个测试用例中,Vihaan 可以执行以下操作:
- 将位置 的路段移动到位置 :$$[{\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].$$
- 将位置 的路段移动到位置 :$$[10,10,{\color{red}8},{\color{red}1}{\color{red}0},12] \rightarrow [10,10,{\color{red}9},{\color{red}9},12].$$
- 将位置 的路段移动到位置 :$$[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 可以首先将位置 的路段移动到位置 :
$$[{\color{red}4},{\color{red}7},5,8] \rightarrow [{\color{red}6},{\color{red}5},5,8].$$然后,他可以将位置 的路段移动到位置 :
$$[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).