머리 묶기

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

요약

한 구간을 골라 그 구간의 모든 값을 구간 전체의 XOR 값으로 바꾸는 연산을 반복해 3을 모두 없애는 최소 횟수를 구하고, 불가능하면 -1을 출력한다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 그리디, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

시현이는 사람들의 헤어 스타일을 바꾸어 묶는 것을 좋아한다. 사람들의 헤어 스타일에는 $0$ (생머리), $1$ (포니테일), $2$ (양갈래), $3$ (세갈래)이 있다.

시현이는 사람들의 헤어스타일 $A\_1, A\_2, \cdots, A\_N$ 이 있을 때, $l$ 과 $r$ 을 적절히 골라 $l$ 번째부터 $r$ 번째까지 사람의 헤어 스타일을 동시에 $A\_l \oplus A\_{l+1} \oplus \cdots \oplus A\_r$ 로 바꿀 수 있다. $\oplus$ 는 Bitwise XOR 연산자이다.

시현이는 모양이 이상한 세갈래를 싫어해서, 어떤 사람의 헤어 스타일도 세갈래가 아니도록 만들려고 한다. 사람들의 헤어 스타일을 바꾸는 최소 횟수를 구해 보자.

입력

입력은 여러 개의 테스트케이스로 이루어져 있다. 입력의 첫째 줄에는 테스트케이스의 수 $T$ 가 주어진다. ( $1 \le T \le 20\\,000$ )

각 테스트케이스의 첫째 줄에는 $N$ 이 주어진다. ( $1 \leq N \leq 10^6$ )

둘째 줄에는 $N$ 명의 헤어 스타일 $A\_1, A\_2, \cdots, A\_N$ 이 공백으로 구분되어 주어진다. ( $0 \leq A\_i \leq 3$ )

모든 테스트케이스의 $N$ 의 합은 $10^6$ 을 초과하지 않는다.

출력

각 테스트케이스마다 한 줄에, 세갈래가 없도록 할 수 있다면 헤어 스타일을 바꾸는 최소 횟수를, 어떻게 바꾸어도 세갈래가 남는다면 $-1$ 을 출력한다.

예제1

예제 1

입력

예상 출력