Hôm nay những chú bò đặc biệt nghịch ngợm! Farmer John chỉ muốn chụp một bức ảnh các chú bò đứng thành hàng, nhưng chúng cứ di chuyển ngay trước khi ông kịp bấm máy.

Cụ thể, mỗi con trong số \(N\) con bò của FJ (\(1 \le N \le 10^5\)) có chiều cao nguyên từ \(1\) đến \(N\). FJ muốn chụp các chú bò đứng thành hàng theo một thứ tự rất cụ thể. Nếu chiều cao của chúng từ trái sang phải là \(h_1, \dots, h_K\), ông muốn dãy chiều cao thỏa mãn ba tính chất sau:

• Chiều cao tăng rồi giảm. Nói chính xác, phải tồn tại một số nguyên \(i\) sao cho \(h_1 \le \dots \le h_i \ge \dots \ge h_K\).
• Không có hai con bò đứng cạnh nhau có chiều cao bằng hệt nhau. Nói chính xác, \(h_i \neq h_{i+1}\) với mọi \(1 \le i < K\).
• Bức ảnh phải đối xứng. Nói chính xác, nếu \(i+j=K+1\) thì \(h_i=h_j\).

FJ muốn bức ảnh có nhiều bò nhất có thể. Cụ thể, FJ có thể loại bỏ một số con bò và sắp xếp lại những con còn lại. Hãy tính số bò tối đa có thể xuất hiện trong ảnh mà vẫn thỏa mãn các yêu cầu của ông.

Dữ liệu vào

Bạn phải trả lời nhiều bộ dữ liệu.

Dòng đầu tiên chứa một số nguyên \(T\) (\(1 \leq T \leq 10^5\)), là số bộ dữ liệu. Sau đó là \(T\) bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên \(N\). Dòng thứ hai chứa \(N\) số nguyên là chiều cao của \(N\) con bò hiện có. Mỗi chiều cao nằm trong khoảng từ \(1\) đến \(N\).

Đảm bảo tổng \(N\) trên tất cả các bộ dữ liệu không vượt quá \(10^6\).

Dữ liệu ra

In ra \(T\) dòng; dòng thứ \(i\) chứa đáp án cho bộ dữ liệu thứ \(i\). Mỗi dòng là một số nguyên biểu thị số bò tối đa FJ có thể đưa vào bức ảnh.

Ví dụ

2
4
1 1 2 3
4
3 3 2 1

3
1

Phân nhóm

• Dữ liệu 2–3: \(T\le 100, N\le 7\).
• Dữ liệu 4–5: \(T\le 10^4\), mọi con bò đều có chiều cao không quá \(10\).
• Dữ liệu 6–11: Không có ràng buộc bổ sung.

Đề bài: Nick Wu.

Nguồn

USACO 2025 US Open Contest, Bronze — More Cow Photos: https://usaco.org/index.php?page=viewproblem2&cpid=1516