说明

给定一个长度为 $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}$。你的任务是确定在执行任意次操作后，数组中最多可以存在多少种不同的值。

$\textbf{注意：}$ $x \ \texttt{and}\ y$ 表示 $x$ 和 $y$ 的按位与。$x \ \texttt{or}\ y$ 表示 $x$ 和 $y$ 的按位或。$x \oplus y$ 表示 $x$ 和 $y$ 的按位异或。

输入格式

• 第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示数组的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示数组的元素。

输出格式

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

2
2 3

4

2
3 4

4

提示

翻译由 DeepSeek V3 完成