Description

对于一个序列 $\{a_n\}$，你可以进行如下操作任意次：

• 选择两个相邻的数 $a_i,a_{i+1}\,(1\leq i < n)$，并在这两个数之间插入一个数，这个数可以是：
  • $a_i \texttt{ and } a_{i+1}$.
  • $a_i \texttt{ or } a_{i+1}$.
  • $a_i \texttt{ xor } a_{i+1}$.

其中 $\texttt{and},\texttt{or},\texttt{xor}$ 代表二进制下的按位与、按位或和按位异或。

你需要使序列中不同的数的个数尽量多，求最终序列中不同的数的个数的最大值。

Format

Input

第一行一个正整数 $n\,(1\leq n\leq 5\times 10^5)$.

第二行 $n$ 个正整数表示序列 $\{a_n\}\,(0\leq a_i < 2^{30})$.

Output

仅一个正整数表示不同的数的个数。

Samples

2
2 3

4

2
3 4

4

Limitation

1s, 256MiB.