석환나라에 전쟁이 일어났다! 석환나라는 엄청나게 큰 이진 트리 모양의 국가로, $1, 2, \cdots, 10^{100}$ 까지 번호가 붙여진 총 $10^{100}$ 개의 도시로 이루어져 있다. 석환나라에는 $10^{100} - 1$ 개의 도로가 있는데, 이 중 $i$번째 도로는 ($1 \le i < 10^{100}$) $\lfloor \frac{i+1}{2} \rfloor$ 번 도시와 $i + 1$ 번 도시를 잇는데, 이를 그림으로 묘사하면 아래와 같다:

총리 윈스턴 아기서콴(\textit{Winston Agiseokhwan})은 위기의 석환나라를 구하는 중대한 임무를 맡고 있다. 석환나라의 적국들은 석환나라의 중요 군시설을 방해하는 데 혈안이 되어 있기 때문에, 석환나라의 국민들을 보호하기 위해서는 군대가 자주 오가는 도시를 우선 방어하는 것이 효과적이다. 석환나라에는 $N$개의 군부대가 서로 다른 도시에 존재하고, 군부대들은 서로 물자나 정보를 주고받기 위해서 오간다. 이 때, 어떠한 도시가 \textbf{위험하다} 는 것은, 해당 도시에 군부대가 있거나, 경로가 해당 도시를 지나는 서로 다른 두 군부대가 존재함을 뜻한다. 석환나라는 트리이고, 경로는 같은 도시를 두번 방문하지 않아야 한다고 정의되기 때문에, 두 군부대를 지나는 경로는 언제나 유일하다는 사실을 유념하자.

아기서콴 총리를 위해, 석환나라에 있는 위험한 도시의 개수를 계산해주자.

Input

첫 번째 줄에 군부대의 수 $N$ 이 주어진다. ($2 \le N \le 250\,000$)

이후 $N$개의 줄에 군부대가 있는 도시의 번호를 나타내는 수열 $A_1, A_2, \cdots, A_N$ 이 주어진다. 주어지는 도시들은 서로 다르다. ($1 \le A_i < 2^{50}$)

Output

석환나라에 있는 위험한 도시의 개수를 출력하라.

Examples

Input 1

4
4 5 6 7

Output 1

7

Input 2

2
1 4294967296

Output 2

33