"Mushrooms are growing!!"
In the Woojung Hall 2 dormitory at Gyeonggi Science High School, various living organisms coexist, including Gyeonggi Science High School students, bees, cockroaches, Jaewoo, unidentified insects, and eggs. Because of this, Woojung Hall 2 is very famous for being environmentally friendly.
Then one day, perhaps being too environmentally friendly, mushrooms started growing in the Woojung Hall 2 shower room!
Automachi Pickle, who hates mushrooms, decided to get rid of all of them.
There are $N$ mushrooms growing in a row in the shower room, and the size of the $i$-th $(1 \le i \le N)$ mushroom is $a_i$.
Pickle uses a special tool to reduce the size of the mushrooms. By using the tool on the $i$-th mushroom and an adjacent $j$-th mushroom, the following effect is achieved:
- The size of the $i$-th mushroom becomes $a_i\, \& \, a_j$. (The & operation is a bitwise AND operation, and its definition is explained in the note below.)
Since Pickle wants to get rid of the mushrooms as quickly as possible to go read the light novel [The Story of PS Where I Make Hanbyeol, Who Claims Competitive Programming is Impossible, Fill Her Streak Thoroughly for 100 Days], he wants to make the size of all mushrooms $0$ by minimizing the number of times the tool is used.
For the lazy Pickle, let's find the minimum number of tool uses!
Input
The first line contains the number of mushrooms $N$.
The second line contains $N$ integers $a_1,\,a_2,\,\cdots,\,a_N$ separated by spaces.
$1 \le N \le 10^6$
$0 \le a_i \le 2^{31}-1 \,(1 \le i \le N,\, a_i$ is an integer$)$
Output
If it is impossible to make the size of all mushrooms $0$, output -1. Otherwise, output the minimum number of tool uses required to make them all $0$.
Subtasks
| Number | Score | Constraints |
|---|---|---|
| 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 | No additional constraints. |
Examples
Input 1
7 1 7 4 6 3 5 9
Output 1
8
Note
Even if the size of the $i$-th mushroom becomes $0$, the $i$-th mushroom does not disappear. That is, even if the size of the $i$-th mushroom becomes $0$, the $(i-1)$-th mushroom and the $(i+1)$-th mushroom do not become adjacent.
The bitwise AND operation is an operation applied digit by digit to two binary values. First, the two given operands are expressed in binary. Then, each digit of the two values is compared; the result is $1$ only if both values have a $1$ at that position, and $0$ otherwise.
For example, the value of $13 \& 7$ is $5$. $13$ in binary is $1101_{(2)}$ and $7$ in binary is $111_{(2)}$. The calculation process is as follows:
