Vào dịp Tết, hai bạn Hạnh và Phúc được cho ~n~ túi kẹo (mỗi túi sẽ có một số viên kẹo), trong đó ~n~ chẵn. Hai bạn nghĩ ra một trò chơi như sau: sắp xếp các túi kẹo thành một dãy với số kẹo trong mỗi túi từ trái sang phải là ~a_1, a_2, ..., a_n~. Ở mỗi lượt, người chơi sẽ chọn một trong hai túi ở bìa trái hoặc bìa phải của dãy rồi ăn hết số kẹo trong đó. Hạnh đi trước và hai bạn thay phiên nhau chơi. Sau ~n~ lượt, cả hai bạn sẽ ăn hết các túi kẹo. Nếu Hạnh có cách chọn các túi kẹo để tổng số kẹo mà bạn ăn được nhiều hơn số kẹo Phúc ăn được thì sẽ thắng, ngược lại thì thua. Cho biết rằng Phúc có ~IQ~ rất cao, hỏi Hạnh có cách chơi để chiến thắng được bạn Phúc hay không?

Input

Dòng 1 là số test ~T~ với ~1 \le T \le 5~.

Mỗi test có 2 dòng: gồm một số nguyên dương ~n~ chẵn và ~n \le 2025.~ Dòng ~2~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~, trong đó ~1 \le a_i \le 10^4.~

Output

Ứng với mỗi test, in ra "YES" - "NO" trên từng dòng cho biết khả năng Hạnh có thắng trò chơi này hay không.

Sample input

1
2
1 2

Sample output

YES

Giải thích

Ở test 1, ta thấy Hạnh có thể ăn túi kẹo bìa phải là thắng.