Cho dãy ~A~ gồm ~N~ số nguyên dương ~a_1,a_2,…,a_N~. Dãy ~A~ có ít nhất hai số hạng mà giá trị của chúng khác nhau.

Yêu cầu: Tìm số dư lớn nhất khi chia ~a_i~ cho ~a_j~ với mọi ~i,j:1 \leq i,j \leq N?~

Input

Vào từ file văn bản CAU3.INP gồm:

• Dòng đầu tiên chứa số nguyên dương ~N~;

• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~a_i~.

Output

Ghi ra file văn bản CAU3.OUT gồm một dòng ghi một số nguyên dương là số dư lớn nhất tìm được.

Scoring

• Subtask ~1~ ~(30\%)~ số tests tương ứng với ~30\%~ số điểm có ~1 < N \leq 7500, 0 < a_i \leq 10^{17}~.

• Subtask ~2~ ~(30\%)~ số tests khác tương ứng với ~30\%~ số điểm có ~1 < N \leq 5.10^5, 0 < a_i \leq 10^{17}~.

• Subtask ~3~ ~(40\%)~ số tests còn lại tương ứng với ~40\%~ số điểm có ~1 < N \leq 5.10^5, 0 < a_i \leq 10^{50}~.

Example input 1

5
3
12
5
8
5

Example output 1

8