← 返回题目列表

Codeforces · 2029/C

C. 新评级

中文机器翻译题面 查看原题

Kevin 曾经是 Codeforces 的参与者。最近,KDOI 团队开发了一款新的在线法官,名为 Forcescode。

Kevin 参加了 Forcescode 上的 $$$n$$$ 竞赛。在第 $$$i$$$ 次比赛中,他的表现评分为 $$$a_i$$$。

现在他已经侵入了Forcescode的后端,并且会选择一个区间$$$[l,r]$$$ ($$$1\le l\le r\le n$$$),然后跳过该区间内的所有比赛。之后,他的评分将按以下方式重新计算:

- 最初,他的评级为$$$x=0$$$;
- 对于每$$$1\le i\le n$$$,第$$$i$$$次比赛后,如果$$$l\le i\le r$$$,则跳过本次比赛,评分保持不变; 否则,他的评分将按照以下规则更新:如果$$$a_i>x$$$,他的评分$$$x$$$将增加$$$1$$$; 如果$$$a_i=x$$$,他的评级$$$x$$$将保持不变; 如果$$$a_i<x$$$,他的评级$$$x$$$将减少$$$1$$$。

如果 Kevin 最佳地选择区间 $$$[l,r]$$$,你必须帮助他在重新计算后找到他的最大可能评级。请注意,凯文必须至少跳过一场比赛。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1\le t\le 5\cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$) - 比赛数量。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$) — 比赛中的表现评分。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 如果 Kevin 选择最佳间隔,则重新计算后的最大可能评分。

示例

输入 #1

5
6
1 2 3 4 5 6
7
1 2 1 1 1 3 4
1
1
9
9 9 8 2 4 4 3 5 3
10
1 2 3 4 1 3 2 1 1 10

输出 #1

5
4
0
4
5

注意

在第一个测试用例中,Kevin 必须跳过至少一场比赛。如果他选择任何长度$$$1$$$的区间,重新计算后他的评级将等于$$$5$$$。

在第二个测试用例中,Kevin 的最佳选择是选择区间 $$$[3,5]$$$。在重新计算期间,他的评分变化如下:

$$$$$$ 0 \xrightarrow{a_1=1} 1 \xrightarrow{a_2=2} 2 \xrightarrow{\mathtt{跳过}} 2 \xrightarrow{\mathtt{跳过}} 2 \xrightarrow{\mathtt{跳过}} 2 \xrightarrow{a_6=3} 3 \xrightarrow{a_7=4} 4 $$$$$$

在第三个测试用例中,Kevin 必须跳过唯一的比赛,因此他的评分将保持初始值 $$$0$$$。

在第四个测试用例中,Kevin 的最优选择是选择区间 $$$[7,9]$$$。在重新计算期间,他的评分变化如下:

$$$$$$ 0 \xrightarrow{a_1=9} 1 \xrightarrow{a_2=9} 2 \xrightarrow{a_3=8} 3 \xrightarrow{a_4=2} 2 \xrightarrow{a_5=4} 3 \xrightarrow{a_6=4} 4 \xrightarrow{\mathtt{跳过}} 4 \xrightarrow{\mathtt{跳过}} 4 \xrightarrow{\mathtt{跳过}} 4 $$$$$$

在第五个测试用例中,Kevin 的最优选择是选择区间 $$$[5,9]$$$。