Bất nghĩa Du hí
Xem PDFAoi Todo là học sinh năm 3 của Trường chuyên Chú thuật Kyoto. Anh ta sở hữu một sức mạnh rất khủng khiếp dù chỉ là một học sinh. Trong sự kiện "Bách quỷ Dạ hành", một mình anh ta đã thanh tẩy 5 nguyền hồn cấp 1 mà không cần sử dụng thuật thức. Aoi Todo chỉ sử dụng thuật thức "Bất nghĩa Du hí" của mình khi đối đầu với nguyền hồn Đặc cấp ngày hôm đó. Nhờ chiến công này mà anh ta đã ngay lập tức được danh hiệu Chú thuật sư cấp 1.
Aoi Todo rất hâm mộ Takada-Chan, một cô nàng idol vô cùng nổi tiếng. Todo đã mua \(N\) quà lưu niệm của Takada-Chan. Ban đầu các món quà được xếp trên kệ thành một hàng ngang, món thứ \(i\) từ trái sang phải có kích thước \(a_i\), và mỗi món đồ sẽ đang quay về bên phải.
Todo muốn sắp xếp các món quà này theo thứ tự kích thước không giảm từ trái sang phải và sau khi sắp xếp các món đồ sẽ đều quay về phía bên phải. Là một người căm ghét sự nhàm chán, Todo muốn việc sắp xếp quà lưu niệm của thần tượng cũng phải thật đặc biệt. Do đó, anh ta quyết định sẽ sử dụng thuật thức của mình để sắp xếp thay vì dùng tay như người bình thường.
Thuật thức "Bất nghĩa Du hí" của Todo cho phép mỗi lần anh ta vỗ tay, anh ta có thể tráo đổi vị trí của hai món quà lưu niệm bất kỳ nằm cạnh nhau. Sau khi tráo đổi vị trí như vậy, hai món quà cũng sẽ thay đổi hướng quay ban đầu của mình - từ trái sang phải hoặc từ phải sang trái.
Hãy cho biết liệu Todo có thể sắp xếp các món quà lưu niệm theo ý muốn của mình được hay không?
Input
- Phần input bao gồm nhiều testcase. Dòng đầu tiên bao gồm số \(t\) (\(1 \leq t \leq 50\)) - số lượng testcase
- Dòng đầu tiên của mỗi testcase bao gồm số nguyên \(n\) (\(1 \leq n \leq 10^5\)) - số lượng quà lưu niệm
- Dòng thứ hai của mỗi testcase bao gồm \(n\) số nguyên \(a_1, a_2, \cdots, a_n\) - kích thước của các món quà
- Dữ liệu đảm bảo tổng các \(n\) không vượt quá \(10^5\)
Output
- In ra "YES" (không có dấu ") nếu tồn tại cách sắp xếp và "NO" (không có dấu ") nếu ngược lại.
Example
Input
3
4
4 3 2 5
4
3 3 2 2
5
1 2 3 5 4Output
YES
YES
NO