Độ lệch

Anna là một học sinh yêu thích toán học, đặc biệt là các bài toán liên quan đến dãy số và phần dư của phép chia hai số nguyên. Theo quan điểm của Anna thì độ lệch của hai số nguyên \(x\) và \(y\) là phần dư của phép chia số lớn cho số bé.

Ví dụ: Với \(x = 7\); \(y = 4\) thì độ lệch của hai số \(x\) và \(y\) là \(3\).

Độ lệch của một dãy số nguyên là độ lệch lớn nhất của hai phần tử bất kì trong dãy đó.

Ví dụ: Với dãy số \(A = (2, 9, 5)\) thì độ lệch của dãy số \(A\) là \(4\).

Yêu cầu: Cho dãy số \(A\) gồm \(N\) phần tử nguyên không âm \(A_1, A_2, \ldots, A_N\). Tìm độ lệch của dãy số \(A\).

Input

Dữ liệu vào gồm hai dòng:

• Dòng 1: Ghi số nguyên \(N\) là số lượng phần tử của dãy số \(A\) (\(1 < N \le 2 \times 10^5\));

• Dòng 2: Ghi \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) (\(0 \le A_i \le 10^6\)).

Ràng buộc:

• Subtask 1: Có \(80\%\) số test ứng với \(80\%\) số điểm có \(N \le 5 \times 10^3\);

• Subtask 2: Có \(20\%\) số test ứng với \(20\%\) số điểm có \(N \le 2 \times 10^5\).

Output

In ra một số nguyên là kết quả của bài toán.

Example

Input:

3
4 2 7

Output:

3

Note

\(4\) chia \(2\) dư \(0\) nên độ lệch của \(4\) và \(2\) là \(0\);

\(7\) chia \(2\) dư \(1\) nên độ lệch của \(7\) và \(2\) là \(1\);

\(7\) chia \(4\) dư \(3\) nên độ lệch của \(7\) và \(4\) là \(3\).

Kết quả cần tìm là \(3\).