17306번 - 전쟁 중의 삶

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

총리 윈스턴 아기서콴(Winston Agiseokhwan)은 위기의 석환나라를 구하는 중대한 임무를 맡고 있다. 석환나라의 적국들은 석환나라의 중요 군 시설을 방해하는 데 혈안이 되어 있기 때문에, 석환나라의 국민들을 보호하기 위해서는 군대가 자주 오가는 도시를 우선 방어하는 것이 효과적이다. 석환나라에는 N개의 군부대가 서로 다른 도시에 존재하고, 군부대들은 서로 물자나 정보를 주고받기 위해서 오간다.

이때, 어떠한 도시가 위험하다는 것은, 해당 도시에 군부대가 있거나, 경로가 해당 도시를 지나는 서로 다른 두 군부대가 존재함을 뜻한다. 석환나라는 트리이고, 경로는 같은 도시를 두 번 방문하지 않아야 한다고 정의되기 때문에, 두 군부대를 지나는 경로는 언제나 유일하다는 사실을 유념하자.

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

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

이후 N개의 줄에 군부대가 있는 도시의 번호를 나타내는 수열 A₁, ..., A_N이 주어진다. 주어지는 도시들은 서로 다르다. (1 ≤ A_i < 2⁵⁰)

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