G. Expanding Array
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \lt 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.

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$$$.

Input

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

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

Examples
Input
2
2 3
Output
4
Input
2
3 4
Output
4