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

Hãy xác định xem dãy ~a~ có bao gồm bất kỳ dãy con có ít nhất ~3~ phần tử lập thành dãy Palindrome.

Notes

• 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ể xóa đi một vài phần tử (hoặc không xóa phần tử nào) để có được dãy ~b~ (và không mất tính thứ tự).
  • Ví dụ: Cho dãy ~a = [1, 2, 1, 3]~:
    • ~[2]~, ~[1, 2, 1, 3]~, ~[2, 3]~ là các dãy con của dãy ~a~.
    • ~[1, 1, 2]~, ~[4]~ không phải là các dãy con của dãy ~a~.
• 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, \dots, 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ụ:
    • ~[1234]~, ~[1, 2, 1]~, ~[1, 3, 2, 2, 3, 1]~ và ~[10, 100, 10]~ là các dãy Palindrome.
    • ~[1, 2]~ và ~[1, 2, 3, 1]~ không phải là các dãy Palindrome.

Input Specification

• Dòng đầu tiên gồm một số nguyên ~t~ ~(1 \le t \le 100)~ - Số lượng truy vấn mà bạn phải trả lời.
• ~2 \times t~ dòng tiếp theo, mỗi cặp ~2~ dòng mô tả một truy vấn như sau:
  • Dòng thứ nhất của truy vấn 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 truy vấn gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le n)~, với ~a_i~ là phần tử thứ ~i~ của dãy ~a~.
• Dữ liệu đầu vào đảm bảo tổng của ~n~ trên tất cả các truy vấn không vượt quá ~10^5~, tức ~\displaystyle \sum_{i = 0}^{t - 1} n_i \le 10^5~.

Output Specification

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

Subtasks

• Subtask 1 [30%]: ~\displaystyle \sum_{i = 0}^{t - 1} n_i \le 5000~.
• Subtask 2 [70%]: Không có giới hạn gì thêm.

Sample Cases

Input #1:

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

Output #1:

YES
YES
NO
YES
NO