Symmetric Clearing

Interview

Time limit2sMemory limit1024 MB

Summary

Given n trees around a circle, each birch or pine, decide whether some line through the center reflects the circle onto itself.

Level: Medium5 of 10
Topics: String, String matching, Array
Solved: No attempts yet

Problem

There are many forests, but not every one of them is magical. A forest must satisfy many conditions to be magical. These conditions are not fully studied yet, but one is known for certain: a forest cannot be magical if it has no round symmetric clearing. For simplicity, consider a forest with birch and pine trees. This forest has exactly one round clearing. Around it grow $n$ trees. Each tree is either a pine or a birch. An axis of the clearing is a straight line that passes through the center of the clearing and splits it into two halves. If the line passes through a tree, that tree belongs to both halves. If one half is symmetric to the other, the line is a symmetry axis and the clearing is symmetric. The following clearings are symmetric (white circles are birches, black circles are pines): This clearing is not symmetric no matter which axis we choose:

Input

The first line contains one integer $T$ ( $1 \le T \le 10$ ), the number of tests. Each test is described by two lines. The first line contains one integer $n$ ( $2 \le n \le 10^5$ ), the number of trees around the clearing. The second line contains $n$ integers $a_i$ ( $0 \le a_i \le 1$ ), describing the trees in clockwise order. $0$ means birch and $1$ means pine.

Output

Print $T$ lines. On line $i$ , print Yes if the clearing in the $i$ -th test has a symmetry axis, and No otherwise.

Examples1

Example 1

Input

4
6
0 1 1 0 1 1
5
0 1 0 1 1
6
1 0 1 0 1 0
6
0 0 1 0 1 1

Expected output

Yes
Yes
Yes
No