33625번 - 버섯이 나 있어!!! 서브태스크

"キノコが生えてる!!" (버섯이 나 있어!!)

경기과학고등학교의 기숙사인 우정 2관에는 경기과학고등학교 학생들, 벌, 바퀴벌레, 재우, 처음 보는 벌레, 달걀🥚 등 다양한 생물들이 공존해서 살고 있다. 이 때문에 우정 2관은 환경 친화적이기로 무척이나 유명하다.

그러다 어느 날, 너무나도 환경 친화적인 나머지 우정 2관 샤워실에 버섯이 자라기 시작했다!

버섯을 싫어하는 오토마치 피클은, 버섯들을 전부 없애버려야겠다고 생각했다.

샤워실에는 $N$송이의 버섯이 일렬로 자라나 있고, $i$ ($1 ≤ i ≤ N$)번째 버섯의 크기는 $a_i$이다.

피클은 특별한 도구를 사용하여 버섯의 크기를 줄인다. $i$번째 버섯과, 그 버섯과 인접한 $j$번째 버섯을 대상으로 하여 도구를 사용하면 다음의 효과를 얻을 수 있다.

• $i$번째 버섯의 크기는 $a_i\, \& \, a_j$가 된다. (& 연산은 bitwise and 연산이며, 정의는 하단 노트에 설명되어 있다.)

피클은 최대한 빨리 버섯을 없애고 라이트 노벨 [경쟁 프로그래밍이라니 절대 무리라고 주장하는 한별이를 백일동안 철저하게 스트릭 채우게 하는 ps 이야기] 를 보러 가고 싶어 하기 때문에, 도구의 사용 횟수를 최소한으로 하여 모든 버섯의 크기를 $0$으로 만들려 한다.

게으른 피클을 위해, 도구의 최소 사용 횟수를 대신 구해 주자!

첫 번째 줄에 버섯의 수 $N$이 주어진다.

두 번째 줄에 $N$개의 수 $a_1,\,a_2,\,\cdots,\,a_N$가 공백으로 구분되어 주어진다.

모든 버섯의 크기를 $0$으로 만드는 것이 불가능하다면 -1을, 가능하다면 $0$으로 만들기 위한 도구 사용 횟수의 최솟값을 출력한다.

• $1 ≤ N ≤ 10^6$
• $0 ≤ a_i ≤ 2^{31}-1 \,(1 ≤ i ≤ N,\, a_i$는 정수$)$

$i$번째 버섯의 크기가 $0$이 되어도 $i$번째 버섯은 사라지지 않는다. 즉, $i$번째 버섯의 크기가 $0$이 되어도 $i-1$번째 버섯과 $i+1$번째 버섯은 인접하지 않는다.

bitwise and 연산은 두 개의 이진수 값에 대해 자리 단위로 적용되는 연산이다. 먼저 피연산자로 주어진 두 값을 2진수로 표현한다. 그 뒤에 두 값의 각 자릿수를 비교해, 두 값 모두에 $1$이 있을 때만 $1$을, 나머지 경우에는 $0$을 계산한다.

예를 들어 $13 \& 7$의 값은 $5$이다. $13$은 2진수로 표현하면 $1101$₍₂₎ 이고 $7$은 2진수로 표현하면 $111$₍₂₎ 이다. 이후의 계산과정은 아래와 같다.