题目描述

体育课上有 $N$ 名同学，同学们排成一队，每个同学有一个体力值 $A_i$，同学们可被看作一个含有 $N$ 个正整数的序列 $A_1, A_2, \cdots, A_N$。

现在老师要带大家做游戏，游戏需把同学们分为三组，为保证游戏的公平性，要求每组同学的体力值之和都完全一致，并且每组内同学的位置要为连续的一段。

换句话说，需要选择两个整数 $L$，$R$，使得 $A_1$ 到 $A_{L - 1}$ 的和等于 $A_L$ 到 $A_R$ 的和等于 $A_{R + 1}$ 到 $A_N$ 的和，且满足 $2 \leq L \leq R \leq N - 1$。

请问老师能否完成一个公平的分组？

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每一组数据：

• 第一行输入一个正整数 $N$，表示序列长度。
• 第二行输入 $N$ 个正整数 $A_1, A_2, \cdots, A_N$ 。

输出格式

对于每组数据，如果可以公平分组则输出 YES，否则输出 NO。

样例

样例1输入

2
5
8 3 5 2 6
5
1 2 3 2 1

样例1输出

YES
YES

样例2输入

1
3
5 6 7

样例2输出

NO

样例说明

在测试样例1中：

• 第一组数据，可以选择将 $L = 2$ 和 $R = 3$ 位置进行分组。
• 第二组数据，可以选择将 $L = 3$ 和 $R = 3$ 位置进行分组。

数据范围与提示

• 对于 50% 的数据，$1 \leq T \leq 10$，$3 \leq N \leq 10^3$，$1 \leq A_i \leq N$ 。
• 对于 100% 的数据，$1 \leq T \leq 10$，$3 \leq N \leq 2 \times 10^5$，$1 \leq A_i \leq 10^9$ 。