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$