Sau khi thành công thiết lập AI, BabyOrange và CandySnowy chưa kịp ăn mừng thì tự nhiên một tiếng réo vang lên. Họ nhận ra bụng họ đã đói vì vậy họ quyết định đến siêu thị để mua đồ ăn.
Khi tới siêu thị, họ bị một đám người lạ bắt cóc. Khi CandySnowy hỏi lý do bắt cóc họ, đám người lạ nói: "Thứ bọn ta muốn chính là hệ thống AI đó, nếu các ngươi không giao nộp cho bọn ta, bọn ta sẽ cho ăn 100 quả chích điện, trừ khi các ngươi giải được câu đố của bọn ta.
Vì không muốn bị ăn 100 quả chích điện 100 vôn, nên BabyOrange và CandySnowy quyết định giải câu đố. Câu đố của bọn họ như sau:
Trong siêu thị, các mặt hàng cùng loại thường đặt cạnh nhau để kệ trông gọn gàng và khách hàng dễ dàng tìm thấy những gì mình cần.
Chiếc kệ được mô tả bởi một mảng \(a\) gồm \(n\) phần tử, trong đó \({a_i}\) là loại hàng hóa tại vị trí \(i\)
Chúng ta nói chiếc kệ được xếp đúng nếu với mỗi hai vị trí \(i\) và \(j\) sao cho \(1 \le i \le j \le n\) và \({a_i} = {a_j}\) thì thỏa mãn điều kiện sau: Với mỗi \(k\) từ \(i\) tới \(j\), \({a_k}\) phải luôn bằng \({a_j}\). Nói cách khác, các hàng hóa cùng loại phải ở liền kề nhau. Ví dụ, giả sử có 2 loại hàng hóa là 1 và 2, thì dãy 1 1 2 2 là xếp đúng, còn 1 2 1 2 là xếp sai.
Bạn được chọn 2 vị trí khác nhau và thay đổi vị trí những hàng hóa này, nhưng bạn chỉ được thay đổi đúng 1 lần. Bạn cũng có thể không thay đổi vị trí hàng hóa nào cả.
Hãy cho biết có thể xếp kệ sao cho đúng được không.
Nghe xong câu đố, BabyOrange và CandySnowy hoàn toàn có thể giải được. Nhưng vì chưa có gì bỏ bụng nên họ đành nhờ các bạn giải dùm.

Input

• Dòng đầu tiên ghi số truy vấn \(t\) \((1 \le t \le 10^4)\)
• Mỗi truy vấn sẽ gồm 2 dòng:
• Dòng đầu tiên chứa số nguyên \(n\) \((2 \le n \le 2 \times 10^5)\) - số lượng hàng hóa trên kệ
• Dòng thứ hai chứa \(n\) số \({a_i}\) \((1 \le {a_i} \le 10^9)\), \({a_i}\) chỉ loại hàng hóa tại vị trí \(i\)

Output

• Với mỗi truy vấn, in ra NO nếu không thể xếp được và YES nếu có thể xếp được kệ đúng chỉ trong một lần thay đổi hàng hóa.

Example

2
3
1 2 1
6
1 2 3 1 2 3

YES
NO

5
2
7 7
6
1 1 2 3 2 3
7
1 2 3 1 2 3 4
6
1 2 1 2 1 1
6
1 2 2 3 3 1

YES
YES
NO
YES
NO