扩展数组

题目描述

给定一个长度为 $n$ 的整数数组 $a _ 1, a _ 2, \ldots, a _ n$ ，可以对该数组执行任意数量的操作。 在每次操作中，你可以选择两个相邻的元素 $a _ i$ 和 $a _ {i+1}$ ( $1 \le i < n$ )，并在它们之间插入以下三个值之一： $a _ i \texttt{ and } a _ {i+1}$ 、 $a _ i \texttt{ or } a _ {i+1}$ 或 $a _ i \oplus a _ {i+1}$ 。 你的任务是确定数组在执行任意数量的操作后，最多可以存在多少个不同的值。

注意： $x \texttt{ and } y$ 表示 $x$ 和 $y$ 在二进制下的位与。 $x \texttt{ or } y$ 表示 $x$ 和 $y$ 在二进制下的位或。 $x \oplus y$ 表示 $x$ 和 $y$ 在二进制下的位 XOR(异或)。

与、或、异或运算真值表

输入格式

第一行包含一个整数 $n$ ( $2 \le n \le 10 ^ 5$ )，表示数组的长度。 第二行包含 $n$ 个整数 $a _ 1, a _ 2, \ldots, a _ n$ ( $0 \le a _ i < 10^9$ )，表示数组的元素。

输出格式

输出一个整数，表示数组在执行任意数量的操作后，最多可以存在多少个不同的值。

样例 1

2
2 3

4

样例 2

2
3 4

4

提示

对于样例1，我们可以执行以下操作：

1. 在下标 $1$ 和 $2$ 之间插入 $2 \texttt{and} 3 = 2$，数组变为 $[2, 2, 3]$。
2. 在下标 $1$ 和 $2$ 之间插入 $2 \oplus 2 = 0$，数组变为 $[2, 0, 2, 3]$。
3. 在下标 $3$ 和 $4$ 之间插入 $2 \oplus 3 = 1$，数组变为 $[2, 0, 2, 1, 3]$。

最终，数组中存在的不同值为 $0, 1, 2, 3$，共计 $4$ 个不同的值。