Cho dãy ~a~ gồm ~n~ số nguyên.

Hãy xác định xem dãy ~a~ có dãy con nào gồm ít nhất ~3~ phần tử lập thành dãy palindrome hay không.

Lưu ý, một dãy ~b~ được gọi là dãy con của dãy ~a~ nếu từ dãy ~a~ ta có thể xoá đi một vài phần tử (hoặc không xoá phần tử nào) để có được dãy ~b~ (và không mất tính thứ tự). Ví dụ, ~[2], [1, 2, 1, 3]~, và ~[2, 3]~ là dãy con của ~[1, 2, 1, 3]~, nhưng ~[1, 1, 2]~ và ~[4]~ thì không.

Đồng thời, một dãy là dãy palindrome khi dãy đó đọc xuôi hay đọc ngược đều như nhau. Hay nói cách khác, một dãy ~a_1, a_2, \ldots , a_n~ là một dãy palindrome nếu ~a_i = a_{n-i+1}~ với mọi ~i~ từ ~1~ đến ~n~. Ví dụ, dãy ~[1234], [1, 2, 1], [1, 3, 2, 2, 3, 1]~, và ~[10, 100, 10]~ là dãy palindrome, nhưng dãy ~[1, 2]~ và ~[1, 2, 3, 1]~ thì không.

Dữ liệu

Dòng đầu tiên gồm một số nguyên ~t~ ~(1 \le t \le 100)~ — số lượng test. Tiếp theo là ~t~ test, mỗi test gồm:

• Dòng đầu tiên của mỗi test case gồm một số nguyên ~n~ ~(3 \le n \le 10^5)~ - độ dài của dãy ~a~.

• Dòng thứ hai của test case gồm ~n~ số nguyên ~a_1, a_2, \ldots , a_n~ ~(1 \le a_i \le n)~, với ~a_i~ là phần tử thứ ~i~ của ~a~.

Dữ liệu đảm bảo tổng của ~n~ trên tất cả các test không vượt quá ~10^5~.

Kết quả

Với mỗi test, in YES nếu ~a~ có ít nhất một dãy con gồm ít nhất ~3~ phần tử lập thành dãy palindrome và NO nếu ngược lại.

Ví dụ

Sample Input

5
3
1 2 1
5
1 2 2 3 2
3
1 1 2
4
1 2 2 1
10
1 1 2 2 3 3 4 4 5 5

Sample Output

YES
YES
NO
YES
NO

Chấm điểm

• Subtask 1 (~30\%~ số test): ~n \le 5000~

• Subtask 2 (~70\%~ số test): Không có ràng buộc gì thêm.