막대기

시간 제한1초메모리 제한128 MB

요약

막대 길이들이 주어질 때, 같은 길이의 막대 두 개를 계속 붙여 길이를 두 배로 만들며, 마지막에 남는 막대의 개수를 구한다.

난이도: 쉬움10점 중 3점
유형: 해시맵, 배열, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

정수 길이를 가진 막대기 여러 개가 주어진다. 길이가 같은 두 막대기는 서로 붙여서 길이가 두 배인 막대기 하나로 만들 수 있다. 같은 길이의 막대기가 하나도 남지 않을 때까지, 즉 모든 막대기의 길이가 서로 달라질 때까지 이 붙이기를 반복한다. 최종적으로 남는 막대기는 몇 개인가?

입력

첫째 줄에 막대기의 개수 $n$ ( $1 \le n \le 100\,000$ )이 주어진다. 둘째 줄에 각 막대기의 길이를 나타내는 $n$ 개의 정수가 주어지며, 각 길이는 $1$ 이상 $1000$ 이하이다.

출력

같은 길이의 막대기를 모두 붙인 뒤 남는 막대기의 개수를 출력한다.

예제3

예제 1
입력
```
10
3 3 3 3 3 3 3 3 3 3
```
예상 출력
```
2
```
예제 2
입력
```
1
7
```
예상 출력
```
1
```
예제 3
입력
```
5
1 2 3 4 5
```
예상 출력
```
5
```