310971: CF1915E. Romantic Glasses

E. Romantic Glassestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Iulia has $n$ glasses arranged in a line. The $i$-th glass has $a_i$ units of juice in it. Iulia drinks only from odd-numbered glasses, while her date drinks only from even-numbered glasses.

To impress her date, Iulia wants to find a contiguous subarray of these glasses such that both Iulia and her date will have the same amount of juice in total if only the glasses in this subarray are considered. Please help her to do that.

More formally, find out if there exists two indices $l$, $r$ such that $1 \leq l \leq r \leq n$, and $a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r} = a_{l + 1} + a_{l + 3} + \dots + a_{r-1}$ if $l$ and $r$ have the same parity and $a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r - 1} = a_{l + 1} + a_{l + 3} + \dots + a_{r}$ otherwise.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the total number of glasses.

The second line of each test case contains $n$ integers $a_1, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the amount of juice in each glass.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output "YES" if there exists a subarray satisfying the condition, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

ExampleInput

6
3
1 3 2
6
1 1 1 1 1 1
10
1 6 9 8 55 3 14 2 7 2
8
1 2 11 4 1 5 1 2
6
2 6 1 5 7 8
9
2 5 10 4 4 9 6 7 8

Output

YES
YES
NO
YES
NO
YES

Note

In the first test case, Iulia can pick $l=1$ and $r=3$. Then she drinks $a_1+a_3=1+2=3$ units and her date drinks $a_2=3$ units of juice.

In the second test case, Iulia can pick $l=2$ and $r=5$. Then she drinks $a_3+a_5=1+1=2$ units and her date drinks $a_2+a_4=1+1=2$ units of juice.

In the third test case no such contiguous subarray works.

In the fourth test case, Iulia can pick $l=2$ and $r=8$. Then she drinks $a_3+a_5+a_7=11+1+1=13$ units and her date drinks $a_2+a_4+a_6+a_8=2+4+5+2=13$ units of juice.

题目大意：
朱莉娅有一排n个装有果汁的玻璃杯，第i个杯子里有a_i单位的果汁。朱莉娅只从编号为奇数的杯子里喝果汁，而她的约会对象只从编号为偶数的杯子里喝。为了给约会对象留下深刻印象，朱莉娅想要找到一个连续的子数组，使得只考虑这个子数组中的杯子时，她和约会对象将拥有相同总量的果汁。请帮助她找到这样的子数组。

更正式地说，需要找出是否存在两个索引l和r（1≤l≤r≤n），使得当l和r同奇偶性时，a_l + a_{l + 2} + a_{l + 4} + ... + a_{r} = a_{l + 1} + a_{l + 3} + ... + a_{r-1}，否则a_l + a_{l + 2} + a_{l + 4} + ... + a_{r - 1} = a_{l + 1} + a_{l + 3} + ... + a_{r}。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——玻璃杯的总数。
每个测试用例的第二行包含n个整数a_1, ..., a_n（1≤a_i≤10^9）——每个杯子中的果汁量。
所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，如果存在满足条件的子数组，则输出"YES"，否则输出"NO"。
答案可以用任何大小写形式输出（例如，"yEs"、"yes"、"Yes"和"YES"都将被视为肯定答案）。题目大意： 朱莉娅有一排n个装有果汁的玻璃杯，第i个杯子里有a_i单位的果汁。朱莉娅只从编号为奇数的杯子里喝果汁，而她的约会对象只从编号为偶数的杯子里喝。为了给约会对象留下深刻印象，朱莉娅想要找到一个连续的子数组，使得只考虑这个子数组中的杯子时，她和约会对象将拥有相同总量的果汁。请帮助她找到这样的子数组。 更正式地说，需要找出是否存在两个索引l和r（1≤l≤r≤n），使得当l和r同奇偶性时，a_l + a_{l + 2} + a_{l + 4} + ... + a_{r} = a_{l + 1} + a_{l + 3} + ... + a_{r-1}，否则a_l + a_{l + 2} + a_{l + 4} + ... + a_{r - 1} = a_{l + 1} + a_{l + 3} + ... + a_{r}。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——玻璃杯的总数。 每个测试用例的第二行包含n个整数a_1, ..., a_n（1≤a_i≤10^9）——每个杯子中的果汁量。 所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，如果存在满足条件的子数组，则输出"YES"，否则输出"NO"。 答案可以用任何大小写形式输出（例如，"yEs"、"yes"、"Yes"和"YES"都将被视为肯定答案）。