Winko - vũ khí súng bắn tia plasma do công ty Q nghiên cứu chế tạo vào thế kỉ 23 có sức công phá cao, được phe Nổi loạn (Rebellion) dự kiến sử dụng trong trận chiến cuối cùng với Đế chế Thiên hà (Galactic Empire). Vũ khí gồm \(n\) thành phần bố trí trên một đường thẳng, các thành phần được tích lượng điện năng lần lượt là \(a_1, a_2, a_3, \ldots, a_n\). Điều kiện để Winko hoạt động được là điện năng của mỗi thành phần phải bé hơn mọi thành phần nằm phía sau nó, tức \(a_i < a_j\) với mọi \(1 \leq i < j \leq n\).

Tuy nhiên, trước khi kịp sử dụng, Đế chế đã âm mưu hủy hoại vũ khí này. Bằng một phát đạn pháo từ trường cực mạnh, điện năng của các thành phần của súng đã bị nhiễu loạn, và không còn kích hoạt được nữa. Phe Nổi loạn cần nhanh chóng sửa chữa vũ khí trước trận chiến quan trọng. Họ có một công cụ sửa chữa đặc biệt. Trong một giây, công cụ này có thể hoán đổi lượng điện năng nằm trong hai thành phần liền kề, sau đó đổi dấu chúng. Tức là, nếu sử dụng công cụ lên thành phần \(1 \leq i < n\), thì \(a_i \leftrightarrow a_{i + 1}\), sau đó \(a_i \leftarrow -a_i, a_{i + 1} \leftarrow -a_{i + 1}\) (Do đặt trong bối cảnh khoa học viễn tưởng, nên năng lượng có thể âm và đổi dấu).

Tuy nhiên, nếu vũ khí không thể nào phục hồi được, phe Nổi loạn sẽ tìm sách lược khác để đối phó với Đế chế. Hỏi, với tình trạng điện năng được cho bởi \(a\), thì có sửa vũ khí về trạng thái có thể kích hoạt được hay không?

Lưu ý rằng vấn đề trên được đặt ra trong \(t\) vũ trụ song song riêng biệt nhau. Trong mỗi tình huống đặt ra, cần phải giải quyết các vấn đề một cách độc lập.

Input

• Dòng đầu tiên chứa số nguyên \(t\) \((1 \le t \le 20)\) là số tình huống riêng biệt cần xử lý.
• Trong \(t\) nhóm dòng tiếp theo, mỗi nhóm có dạng sau:
  • Dòng đầu chứa số nguyên \(n\) \((1 \le n \le 10^5)\) là số thành phần của vũ khí.
  • Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 < |a_i| \le 10^9)\) là lượng điện năng ban đầu trong mỗi thành phần của vũ khí.

Output

• Gồm \(t\) dòng, mỗi dòng chứa YES nếu trong tình huống tương ứng, phe Nổi loạn có thể sửa được vũ khí và NO trong trường hợp còn lại.

Scoring

• Subtask \(1\) (\(32\%\) số điểm): \(n\) là số chẵn và với mọi \(i\) \((1\le i \le n)\), tồn tại \(j \neq i\) sao cho \(a_i + a_j = 0\).
• Subtask \(2\) (\(18\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(27\%\) số điểm): \(n \le 1000\).
• Subtask \(4\) (\(23\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
7
-4 2 1 -5 4 6 3
7
-7 -4 3 3 -2 8 -7
7
1 2 -4 7 -3 5 -5
7
-6 7 2 3 -3 -7 2

YES
NO
NO
NO