Largest remainder

Time limit1sMemory limit1024 MB

Summary

Given N huge positive integers (up to 50 digits), find the maximum value of a_i mod a_j over all ordered pairs i, j. The sequence has at least two distinct values.

Level: Medium6 of 10
Topics: Sorting, Math, Greedy, Implementation
Solved: No attempts yet

Problem

A sequence of $N$ positive integers $a_1, a_2, \ldots, a_N$ is given. The sequence contains at least one pair of values that differ. Write a program max that finds the largest value of the remainder when $a_i$ is divided by $a_j$ , where $i$ and $j$ each take every value from 1 to $N$ .

Input

The first line contains $N$ . The second line contains $a_1, a_2, \ldots, a_N$ , separated by spaces.

Output

Output one integer, the largest remainder sought.

Constraints

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

Examples1

Example 1
Input
```
5
3 12 5 8 5
```
Expected output
```
8
```