AquaMoon và bài toán sắp xếp kỳ lạ

Điểm: 4,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho dãy $n$ số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ . Mỗi phần tử có một hướng (trái hoặc phải); ban đầu, mọi phần tử đều có hướng phải.

Bạn có thể thực hiện thao tác sau bất kì số lần (kể cả $0$ ):

Chọn hai phần tử kề nhau trong dãy, đổi chỗ chúng. Sau khi đổi chỗ, hướng của cả hai phần tử bị đảo (trái thành phải, phải thành trái).

Hãy xác định xem có cách thực hiện một dãy thao tác sao cho đồng thời xảy ra:

Dãy $a$ trở thành không giảm (đọc từ trái sang phải).
Sau cùng, mọi phần tử lại có hướng phải.

In ra YES nếu được, ngược lại in NO.

Mỗi file dữ liệu chứa nhiều bộ test độc lập.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ( $1 \leq t \leq 50$ ) — số bộ test.
Với mỗi bộ test:
- Dòng đầu chứa số nguyên $n$ ( $1 \leq n \leq 10^{5}$ ).
- Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{5}$ ).

Tổng $n$ trong toàn bộ file không vượt quá $10^{5}$ .

Dữ liệu ra

Với mỗi bộ test, in YES hoặc NO trên một dòng. Có thể in chữ hoa/thường tuỳ ý.

Ràng buộc

$1 \leq t \leq 50$
$1 \leq n \leq 10^{5}$
$1 \leq a_{i} \leq 10^{5}$
Tổng $n$ trong cả file không vượt quá $10^{5}$ .

Ví dụ

Input	Output	Giải thích
3 4 4 3 2 5 4 3 3 2 2 5 1 2 3 5 4	YES YES NO	Test 1: đổi $a_{1}, a_{2}$ → $3 4 2 5$ (hướng L L R R); đổi $a_{2}, a_{3}$ → $3 2 4 5$ (L L R R); đổi $a_{1}, a_{2}$ → $2 3 4 5$ (R R R R). Dãy không giảm và mọi hướng đều phải. Test 3: không tồn tại cách.
1 3 3 2 2	YES	Đổi $a_{1}, a_{2}$ rồi $a_{2}, a_{3}$ rồi $a_{1}, a_{2}$ ... thực chất chỉ cần đổi chỗ phần tử ở vị trí $1$ một số chẵn lần để vừa di chuyển đúng vị trí vừa giữ hướng phải.
1 2 4 3	NO	Chỉ có cách đổi chỗ duy nhất nhưng sau đó cả hai có hướng trái.

Bình luận

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