CF2029C.New Rating

你好，Codeforces Forcescode！

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]$ 的情况下，求出重新计算后他可能获得的最大评分。注意，Kevin 必须至少跳过一场比赛。

每个测试用例包含多组数据。输入的第一行包含一个整数 $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 在最优选择区间后重新计算可能获得的最大评分。

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

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

$$0 \xrightarrow{a_1 = 1} 1 \xrightarrow{a_2 = 2} 2 \xrightarrow{\mathtt{skip}} 2 \xrightarrow{\mathtt{skip}} 2 \xrightarrow{\mathtt{skip}} 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{skip}} 4 \xrightarrow{\mathtt{skip}} 4 \xrightarrow{\mathtt{skip}} 4$$

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

由 ChatGPT 4.1 翻译