Thêm Ảnh Bò

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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:

Dãy bitonic: Tồn tại vị trí $i$ sao cho $h_{1} \leq h_{2} \leq \dots \leq h_{i} \geq h_{i + 1} \geq \dots \geq h_{K}$ .
Không lặp kề: $h_{i} \neq h_{i + 1}$ với mọi $1 \leq i < K$ .
Đố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 \leq T \leq 10^{5}$
Tổng $N$ trên tất cả các bộ test $\leq 10^{6}$
Chiều cao trong khoảng $[1, N]$

Ví dụ

Input	Output	Giải thích
2 4 1 1 2 3 4 3 3 2 1	3 1	Bộ 1: Chọn bò chiều cao (1, 3, 1) — tăng rồi giảm, đối xứng, không lặp kề. Bộ 2: Chỉ chọn được 1 bò vì không đủ cặp giống nhau.

Bình luận

Không có bình luận tại thời điểm này.