LED String Rearrangement

Given a series of LED strings, determine whether it is possible to achieve an alternating configuration (no two consecutive LEDs have the same value) by changing the state of at most one LED. An alternating sequence appears as either 1 0 1 0 … or 0 1 0 1 ….

Formally, for each test case you are given a sequence of n LED states (each either 0 or 1). You are allowed to change at most one state in the sequence. Your task is to decide whether such a modification can yield a valid alternating configuration.

inputFormat

The first line of input contains an integer t, the number of test cases. For each test case, the first line contains an integer n (the number of LED strings). The second line contains n space-separated integers (each either 0 or 1) representing the states of the LEDs.

outputFormat

For each test case, output a line with either "Yes" if it is possible to achieve an alternating configuration by changing at most one LED, or "No" otherwise.## sample

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

Yes
No
Yes