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は少なくとも1つのコンテストをスキップしなければなりません。

入力

各テストケースには複数のテストケースが含まれます。入力の最初の行には、テストケースの数を示す単一の整数 $t$ ($1 \le t \le 5 \cdot 10^4$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、コンテストの数を示す単一の整数 $n$ ($1 \le n \le 3 \cdot 10^5$) が含まれます。 2行目には、$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つのコンテストをスキップする必要があります。長さ1の任意の区間を選択した場合、再計算後のレーティングは5になります。

2番目のテストケースでは、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$$

3番目のテストケースでは、Kevinは唯一のコンテストをスキップしなければならないため、レーティングは初期値の0のままとなります。

4番目のテストケースでは、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$$

5番目のテストケースでは、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$$