가장 큰 나머지

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

요약

50자리까지의 큰 양의 정수 N개가 주어질 때, 모든 순서쌍 i, j에 대해 a_i를 a_j로 나눈 나머지의 최댓값을 구한다. 수열에는 서로 다른 값이 적어도 하나 존재한다.

난이도: 보통10점 중 6점
유형: 정렬, 수학, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

양의 정수 $a_1, a_2, \ldots, a_N$ 이 주어진다. 주어진 수열에는 값이 서로 다른 두 수가 적어도 한 쌍 존재한다. $1 \le i, j \le N$ 인 모든 $i, j$ 에 대하여 $a_i$ 를 $a_j$ 로 나눈 나머지의 최댓값을 구하는 프로그램 max를 작성하시오.

입력

첫째 줄에 $N$ 이 주어진다. 둘째 줄에 $a_1, a_2, \ldots, a_N$ 이 공백으로 구분되어 주어진다.

출력

구하는 최대 나머지를 한 줄에 출력한다.

제한

$1 < N < 500\,000$
$0 < a_i < 10^{50}$ , $i = 1, \ldots, N$ .

예제1

예제 1
입력
```
5
3 12 5 8 5
```
예상 출력
```
8
```