"キノコが生えてる!!" (버섯이 나 있어!!)
경기과학고등학교의 기숙사인 우정 2관에는 경기과학고등학교 학생들, 벌, 바퀴벌레, 재우, 처음 보는 벌레, 달걀 등 다양한 생물들이 공존해서 살고 있다. 이 때문에 우정 2관은 환경 친화적이기로 무척이나 유명하다.
그러다 어느 날, 너무나도 환경 친화적인 나머지 우정 2관 샤워실에 버섯이 자라기 시작했다!
버섯을 싫어하는 오토마치 피클은, 이 버섯을 전부 없애버려야겠다고 생각했다.
샤워실에는 $N$개의 버섯이 일렬로 자라나 있고, $i$ $(1 \le i \le N)$번째 버섯의 크기는 $a_i$이다.
피클은 특별한 도구를 사용하여 버섯의 크기를 줄인다. $i$번째 버섯과, 그 버섯과 인접한 $j$번째 버섯을 대상으로 하여 도구를 사용하면 다음의 효과를 얻을 수 있다.
- $i$번째 버섯의 크기는 $a_i\, \& \, a_j$가 된다. (& 연산은 bitwise and 연산이며, 정의는 하단 노트에 설명되어 있다.)
피클은 최대한 빨리 버섯을 없애고 라이트 노벨 [경쟁 프로그래밍이라니 절대 무리라고 주장하는 한별이를 백일동안 철저하게 스트릭 채우게 하는 ps 이야기] 를 보러 가고 싶어 하기 때문에, 도구의 사용 횟수를 최소한으로 하여 모든 버섯의 크기를 $0$으로 만들려 한다.
게으른 피클을 위해, 도구의 최소 사용 횟수를 대신 구해 주자!
Input
첫 번째 줄에 버섯의 수 $N$이 주어진다.
두 번째 줄에 $N$개의 수 $a_1,\,a_2,\,\cdots,\,a_N$가 공백으로 구분되어 주어진다.
$1 \le N \le 10^6$
$0 \le a_i \le 2^{31}-1 \,(1 \le i \le N,\, a_i$는 정수$)$
Output
모든 버섯의 크기를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 0으로 만들기 위한 도구 사용 횟수의 최솟값을 출력한다.
Scoring
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 2 | $a_1\ \&\ a_2\ \&\ \cdots\ \&\ a_N \neq 0$ |
| 2 | 10 | $N=3$ |
| 3 | 18 | $a_1=0$ |
| 4 | 30 | $n\leq5000$ |
| 5 | 40 | 추가 제약 조건 없음. |
Examples
Input 1
7 1 7 4 6 3 5 9
Output 1
8
Note
$i$번째 버섯의 크기가 $0$이 되어도 $i$번째 버섯은 사라지지 않는다. 즉, $i$번째 버섯의 크기가 $0$이 되어도 $i-1$번째 버섯과 $i+1$번째 버섯은 인접하지 않는다.
bitwise and 연산은 두 개의 이진수 값에 대해 자리 단위로 적용되는 연산이다. 먼저 피연산자로 주어진 두 값을 2진수로 표현한다. 그 뒤에 두 값의 각 자릿수를 비교해, 두 값 모두에 $1$이 있을 때만 $1$을, 나머지 경우에는 $0$을 계산한다.
예를 들어 $13 \& 7$의 값은 $5$이다. $13$은 2진수로 표현하면 $1101_{(2)}$ 이고 $7$은 2진수로 표현하면 $111_{(2)}$ 이다. 이후의 계산과정은 아래와 같다.
