Symmetrical Glade#2548
There are many forests, but not every forest is magical. For a forest to be magical, certain conditions must be fulfilled. While not all of these conditions are fully understood, one thing is clear: a forest cannot be magical without a round symmetrical clearing.
Let us consider, for simplicity, a forest where only birch and pine trees grow. There is exactly one round clearing in this forest. Around it, there are trees. Each tree is either a pine or a birch. The axis of the clearing is a straight line passing through its center and dividing it into two halves. If this line passes through a tree, then that tree belongs to both halves. If, in this case, one half is a mirror image of the other, then the line is an axis of symmetry and the clearing is symmetrical. Thus, the following clearings are symmetrical (white circles represent birches, black circles represent pines):
But this clearing is not symmetrical, no matter which axis is chosen:
The first line of the input contains a single integer (1 \leq T \leq 10) — the number of test cases. Then blocks follow, each describing a test case.
Each test description consists of two lines. The first line contains an integer (2 \leq n \leq 10^5) — the number of trees surrounding the clearing. The second line contains integers a_i (0 \leq a_i \leq 1), describing the trees that surround the clearing in clockwise order. corresponds to a birch, to a pine.
Print lines in the output, containing the answers to the test cases. In the line with number , print Yes if the corresponding clearing has an axis of symmetry, and No otherwise.
Example 1