Dãy con gần tăng dài nhất

Một dãy $b_1,b_2,\dots ,b_k$ được gọi là gần tăng nếu:

$$min(b_1,b_2)\le min(b_2,b_3)\le \dots \le min(b_{k-1},b_k).$$

Mọi dãy có không quá hai phần tử đều được coi là gần tăng.

Cho dãy số nguyên $a_1,a_2,\dots ,a_n$. Hãy tính độ dài lớn nhất của một dãy con (không cần liên tiếp) gần tăng của $a$.

Một dãy con của $a$ là dãy thu được bằng cách xóa đi một số phần tử (có thể không xóa) trong $a$ mà giữ nguyên thứ tự các phần tử còn lại.

Có $t$ test case độc lập trong một file dữ liệu.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$ — số lượng test case.
• Với mỗi test case:
  • Dòng đầu chứa một số nguyên $n$ — độ dài dãy.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi test case, in ra một số nguyên — độ dài lớn nhất của dãy con gần tăng của $a$.

Ràng buộc

• $1\le t\le 1000$
• $2\le n\le 5·{10}^5$
• $1\le a_i\le n$
• Tổng $n$ trên tất cả test case không vượt quá $5·{10}^5$.

Ví dụ