대칭 공터

면접 대비

시간 제한2초메모리 제한1024 MB

요약

원형으로 둘러선 n그루의 나무가 자작나무인지 소나무인지 주어질 때, 중심을 지나는 대칭축이 있는지 판별합니다.

난이도: 보통10점 중 5점
유형: 문자열, 문자열 매칭, 배열
정답자: 아직 제출이 없습니다

문제

숲은 많지만 그중 모든 숲이 마법의 숲은 아니다. 숲이 마법의 숲이 되려면 많은 조건을 만족해야 한다. 그 조건들은 아직 충분히 연구되지 않았지만, 한 가지는 확실히 알려져 있다. 둥근 대칭 공터가 없는 숲은 마법의 숲일 수 없다. 단순하게 자작나무와 소나무가 자라는 숲을 생각하자. 이 숲에는 둥근 공터가 하나 있다. 공터 둘레에는 $n$ 그루의 나무가 자란다. 각 나무는 소나무 또는 자작나무다. 공터의 축은 공터의 중심을 지나 공터를 두 반쪽으로 나누는 직선이다. 축이 어떤 나무를 지나면 그 나무는 두 반쪽에 모두 속한다. 한쪽 반쪽이 다른 쪽과 대칭이면 그 직선은 대칭축이고 공터는 대칭이다. 다음 공터들은 대칭이다(흰 원은 자작나무, 검은 원은 소나무). 다음 공터는 어떤 축을 골라도 대칭이 아니다.

입력

첫 줄에 테스트의 개수 $T$ ( $1 \le T \le 10$ )가 주어진다. 각 테스트는 두 줄로 이루어진다. 첫 줄에는 공터 둘레의 나무 수 $n$ ( $2 \le n \le 10^5$ )이 주어진다. 둘째 줄에는 나무를 시계 방향 순서로 나타내는 정수 $a_i$ ( $0 \le a_i \le 1$ ) $n$ 개가 주어진다. 0은 자작나무, 1은 소나무를 뜻한다.

출력

$T$ 개의 줄을 출력한다. i번째 줄에는 i번째 테스트의 공터에 대칭축이 있으면 Yes, 없으면 No를 출력한다.

예제1

예제 1

입력

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

예상 출력

Yes
Yes
Yes
No