题目描述

Given an integer array $a_1, a_2, \ldots, a_n$ of length $n$, you can perform any number of operations on this array. In each operation, you can choose two adjacent elements $a_i$ and $a_{i+1}$ ($1 \le i < n$), and insert one of the following three values between them: $a_i \ \texttt{and}\ a_{i+1}$, $a_i \ \texttt{or}\ a_{i+1}$, or $a_i \oplus a_{i+1}$. Your task is to determine the maximum number of distinct values that can exist in the array after performing any number of operations.

$\textbf{Note:}$ $x \ \texttt{and}\ y$ represents the bitwise AND of $x$ and $y$. $x \ \texttt{or}\ y$ represents the bitwise OR of $x$ and $y$. $x \oplus y$ represents the bitwise XOR (exclusive OR) of $x$ and $y$.

输入格式

The first line contains a single integer $n$ ($2 \le n \le 10^5$), representing the length of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), representing the elements of the array.

输出格式

Output a single integer, representing the maximum number of distinct values that can be obtained in the array after performing any number of operations.

2
2 3

4

2
3 4

4