Problem Description

Alice has $n$ positive integers, numbered from $1 \sim n$, which are $a_1, a_2, \dots, a_n$.
Bob has just learned the modulo operation, so he uses these $n$ numbers to practice. He wrote down all values of

where $\bmod$ denotes the modulo operation.

Alice wants to know the strict second largest value among all results. Deduplicate all values obtained after modulo, meaning that identical results are kept only once. The second largest value among the remaining numbers is called the strict second largest value.

Input Format

The first line contains a positive integer $n$, representing the number of integers.
The second line contains $n$ positive integers $a_i$.

Output Format

Output one integer in a single line, representing the answer.
If there are fewer than two numbers left after deduplicating the modulo results, output $-1$.

4
4 5 5 6

4

4
1 1 1 1

-1

7
12 3 8 5 7 20 15

12

Hint

【Constraints】
For $40\%$ of the testdata, $1 \le n, a_i \le 100$;
For $70\%$ of the testdata, $1 \le n \le 3000$, $1 \le a_i \le 10^5$;
For $100\%$ of the testdata, $3 \le n \le 2 \times 10^5$, $1 \le a_i \le 10^9$.

【Sample $1$ Explanation】
All modulo results are $\{4,4,4,1,0,5,1,0,5,2,1,1\}$.
After deduplication, we have $\{0,1,2,4,5\}$, so the result is $4$.

Translated by ChatGPT 5