War has broken out in Seokhwan-nara! Seokhwan-nara is a country shaped like an enormous binary tree, consisting of $10^{100}$ cities numbered $1, 2, \cdots, 10^{100}$. There are $10^{100} - 1$ roads in Seokhwan-nara, where the $i$-th road ($1 \le i < 10^{100}$) connects city $\lfloor \frac{i+1}{2} \rfloor$ and city $i + 1$. This is illustrated in the figure below:

Prime Minister Winston Agiseokhwan is tasked with the critical mission of saving Seokhwan-nara from crisis. Since enemy nations are desperate to disrupt Seokhwan-nara's vital military facilities, it is effective to prioritize the defense of cities frequently traversed by the military to protect the citizens. There are $N$ military units located in distinct cities, and these units travel between each other to exchange supplies and information. A city is defined as dangerous if there is a military unit located in that city, or if there exist two distinct military units such that the path between them passes through that city. Keep in mind that since Seokhwan-nara is a tree and a path is defined as not visiting the same city twice, the path between any two military units is always unique.

Help Prime Minister Agiseokhwan by calculating the number of dangerous cities in Seokhwan-nara.

Input

The first line contains the number of military units $N$ ($2 \le N \le 250\,000$).

The following $N$ lines contain the sequence $A_1, A_2, \cdots, A_N$, representing the city numbers where the military units are located. The given cities are all distinct ($1 \le A_i < 2^{50}$).

Output

Output the number of dangerous cities in Seokhwan-nara.

Examples

Input 1

4
4 5 6 7

Output 1

7

Input 2

2
1 4294967296

Output 2

33