Kevin từng là một người tham gia Codeforces. Gần đây, Đội KDOI đã phát triển một hệ thống chấm bài trực tuyến mới có tên là Forcescode.

Kevin đã tham gia $n$ cuộc thi trên Forcescode. Trong cuộc thi thứ $i$, điểm đánh giá (rating) của anh ấy là $a_i$.

Giờ đây, anh ấy đã thâm nhập vào hệ thống của Forcescode và sẽ chọn một đoạn $[l, r]$ ($1 \le l \le r \le n$), sau đó bỏ qua tất cả các cuộc thi trong đoạn này. Sau đó, rating của anh ấy sẽ được tính toán lại theo cách sau:

• Ban đầu, rating của anh ấy là $x = 0$;
• Với mỗi $1 \le i \le n$, sau cuộc thi thứ $i$:
  • Nếu $l \le i \le r$, cuộc thi này sẽ bị bỏ qua và rating không thay đổi;
  • Ngược lại, rating của anh ấy sẽ được cập nhật theo các quy tắc sau:
    • Nếu $a_i > x$, rating $x$ sẽ tăng thêm 1;
    • Nếu $a_i = x$, rating $x$ sẽ không thay đổi;
    • Nếu $a_i < x$, rating $x$ sẽ giảm đi 1.

Bạn hãy giúp Kevin tìm rating cao nhất có thể sau khi tính toán lại nếu anh ấy chọn đoạn $[l, r]$ một cách tối ưu. Lưu ý rằng Kevin phải bỏ qua ít nhất một cuộc thi.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $t$ ($1 \le t \le 5 \cdot 10^4$) — số lượng bộ dữ liệu. Tiếp theo là mô tả các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên duy nhất $n$ ($1 \le n \le 3 \cdot 10^5$) — số lượng cuộc thi.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — điểm đánh giá trong các cuộc thi.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $3 \cdot 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất — rating cao nhất có thể sau khi tính toán lại nếu Kevin chọn đoạn $[l, r]$ tối ưu.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

5
4
0
4
5

Ghi chú

Trong bộ dữ liệu đầu tiên, Kevin phải bỏ qua ít nhất một cuộc thi. Nếu anh ấy chọn bất kỳ đoạn nào có độ dài 1, rating của anh ấy sau khi tính toán lại sẽ bằng 5.

Trong bộ dữ liệu thứ hai, lựa chọn tối ưu của Kevin là chọn đoạn $[3, 5]$. Trong quá trình tính toán lại, rating của anh ấy thay đổi như sau:

$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$

Trong bộ dữ liệu thứ ba, Kevin phải bỏ qua cuộc thi duy nhất, vì vậy rating của anh ấy sẽ giữ nguyên ở giá trị ban đầu là 0.

Trong bộ dữ liệu thứ tư, lựa chọn tối ưu của Kevin là chọn đoạn $[7, 9]$. Trong quá trình tính toán lại, rating của anh ấy thay đổi như sau:

$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$

Trong bộ dữ liệu thứ năm, lựa chọn tối ưu của Kevin là chọn đoạn $[5, 9]$.