It's a Mod, Mod, Mod, Mod World 2

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

요약

서로 다른 양의 정수 N개로 이루어진 집합에서, 1보다 큰 어떤 정수 K로 나눈 나머지가 모두 같은 최대 부분집합의 크기를 구한다.

문제

서로 다른 양의 정수 $N$ 개로 이루어진 집합 $A$ 가 주어진다. $A$ 의 부분집합과 $1$ 보다 큰 정수 $K$ 를 적절히 골라, 부분집합의 모든 원소를 $K$ 로 나눈 나머지가 서로 같게 하려고 한다.

고를 수 있는 부분집합의 최대 크기를 구하여라.

첫째 줄에 집합 $A$ 의 크기 $N$ 이 주어진다. ( $1 \leq N \leq 20\\,000$ )

둘째 줄에 $A$ 의 원소를 의미하는 $N$ 개의 정수 $A\_1, A\_2, \cdots, A\_N$ 이 공백으로 구분되어 주어진다. ( $1 \leq A\_i \leq 10^9$ )

$A$ 의 모든 원소는 서로 다르다.

고를 수 있는 부분집합의 최대 크기를 출력한다.