杂题——Romantic Glasses

Romantic Glasses

原题

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).

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
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.

翻译

尤莉亚 (Iulia) 的 $n$ 眼镜排成一排。第 $i$ 个玻璃杯中有 $a_i$ 单位的果汁。尤莉亚只用奇数杯喝酒，而她的约会对象只用偶数杯喝酒。

为了给她的约会对象留下深刻印象，尤莉亚想要找到这些玻璃杯的连续子数组，这样，如果仅考虑该子数组中的杯子，尤莉亚和她的约会对象将拥有相同数量的果汁。请帮助她做到这一点。

更正式地说，如果 $l$ 和 $r$ 具有相同的奇偶性，则找出是否存在两个索引 $l$ 、 $r$ 使得 $1 \leq l \leq r \leq n$ 和 $a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r} = a_{l + 1} + a_{l + 3} + \dots + a_{r-1}$ 具有相同的奇偶性，否则为 $a_l + a_{l + 2} + a_{l + 4} + \dots + a_{r - 1} = a_{l + 1} + a_{l + 3} + \dots + a_{r}$ 。

输入

第一行包含一个整数 $t$ ( $1 \leq t \leq 10^4$ ) - 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) - 眼镜总数。

每个测试用例的第二行包含 $n$ 整数 $a_1, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ) - 每杯果汁的量。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，如果存在满足条件的子数组，则输出“YES”，否则输出“NO”。

您可以在任何情况下输出答案（例如，字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案）。

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
YES
YES
NO
YES
NO
YES

笔记

在第一个测试用例中，Iulia 可以选择 $l=1$ 和 $r=3$ 。然后她喝了 $a_1+a_3=1+2=3$ 单位，她的约会对象喝了 $a_2=3$ 单位果汁。

在第二个测试用例中，Iulia 可以选择 $l=2$ 和 $r=5$ 。然后她喝了 $a_3+a_5=1+1=2$ 单位，她的约会对象喝了 $a_2+a_4=1+1=2$ 单位果汁。

在第三个测试用例中，没有这样的连续子数组起作用。

在第四个测试用例中，Iulia 可以选择 $l=2$ 和 $r=8$ 。然后她喝了 $a_3+a_5+a_7=11+1+1=13$ 单位，她的约会对象喝了 $a_2+a_4+a_6+a_8=2+4+5+2=13$ 单位果汁。

思路

​ 问题大概可以描述为这样一个问题:给定一个数组，判断是否存在一个区间使得其中所有奇数下标元素之和等于偶数下标元素之和.我们可以对数组重新赋值，奇数位赋值为负数，偶数位不变。这样我们后面求前缀和，只要看有没有一段区间和为零的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>
 
// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long LL;
typedef double db;
 
 
const int INF = 1e9;
const int N = 2e5 + 10;
 
LL arr[N];
 
void solve() {
    int n;
    cin>>n;
    fore (i, 1, n) {
        int x;
        cin>>x;
        if(i%2==0) arr[i]=x;
        if(i%2!=0) arr[i]=-x;
    }
 
    //用set判重，当前面出现过和这个前缀和相等值的前缀和，那么这两个之间的区间和是0.
    // s[a]-s[b-1]---->a到b之间的区间和。
 
    set<LL> s;
 
    //注意如果前缀和本身就是0，那么就不需要和其他前缀和组合也能满足情况。
    s.insert(0);    
 
    fore (i, 1, n){
        arr[i]+=arr[i-1];
 
        if(s.count(arr[i])){
            cout<<"YES"<<ed;
            return;
        }
 
        s.insert(arr[i]);
    }
    cout<<"NO"<<ed;
}
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    re;
}