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, \dots, 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{\text{skip}} 2 \xrightarrow{\text{skip}} 2 \xrightarrow{\text{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{\text{skip}} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{\text{skip}} 4$

在第五个测试用例中，Kevin 的最优选择是区间 $[5, 9]$。重新计算过程中，他的评分变化如下： $0 \xrightarrow{a_1=1} 1 \xrightarrow{a_2=2} 2 \xrightarrow{a_3=3} 3 \xrightarrow{a_4=4} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{\text{skip}} 4 \xrightarrow{\text{skip}} 4$