Double Up

면접 대비

시간 제한2초메모리 제한1024 MB

요약

각 수는 홀수 부분이 같은 수와만 같은 값이 되므로, 홀수 부분이 같은 수의 최대 개수를 구합니다.

문제

$N$ 개의 양의 정수로 이루어진 수열 $A$ 가 주어진다. 달구는 이 수열에서 수 하나를 골라 $2$ 를 곱하는 작업을 원하는 만큼 수행할 수 있다.

달구가 모든 작업을 마친 뒤, 배열에서 가장 많이 등장하는 수를 $k$ 라 하자. 가장 많이 등장하는 수가 여러 개라면 그중 가장 큰 수를 $k$ 라 한다. $k$ 의 등장 횟수가 가질 수 있는 최댓값을 구하시오.

첫째 줄에 수열의 길이 $N$ 이 주어진다. $(1 \le N \le 200\ 000)$

둘째 줄에 $N$ 개의 양의 정수 $A_1, A_2, \cdots, A_N$ 이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$

작업을 원하는 만큼 수행한 뒤, 배열에서 가장 많이 등장하는 수의 최대 등장 횟수를 출력한다.