Thêm Ảnh Bò

Farmer John muốn chụp ảnh một số con bò xếp thành hàng. Dãy chiều cao phải thỏa mãn ba điều kiện:

1. Dãy bitonic: Tồn tại vị trí $i$ sao cho $h_1\le h_2\le \dots \le h_i\ge h_{i+1}\ge \dots \ge h_K$.
2. Không lặp kề: $h_i\ne h_{i+1}$ với mọi $1\le i<K$.
3. Đối xứng: Nếu $i+j=K+1$ thì $h_i=h_j$.

Có $T$ bộ test. Mỗi bộ test cho $N$ con bò với chiều cao từ $1$ đến $N$ (có thể trùng). Hãy chọn và sắp xếp một tập con bò lớn nhất thỏa mãn cả ba điều kiện.

Dữ liệu vào

• Dòng 1: Số nguyên $T$.
• Mỗi bộ test:
  • Dòng 1: Số nguyên $N$.
  • Dòng 2: $N$ số nguyên — chiều cao các con bò.

Dữ liệu ra

• $T$ dòng, mỗi dòng là số con bò tối đa.

Ràng buộc

• $1\le T\le {10}^5$
• Tổng $N$ trên tất cả các bộ test $\le {10}^6$
• Chiều cao trong khoảng $[1,N]$

Ví dụ