posta

Poștașul Algorel are de livrat colete la $n$ case de pe Strada Progresiilor, la numerele cunoscute $a_1, a_2, \ldots, a_n$. El are un algoritm propriu de vizitare a unor case de pe stradă, chiar dacă nu are pachete pentru toate acestea. La început Algorel alege un număr $x$, vizitează casa cu numărul $1$, iar apoi fiecare casă vizitată se află la un număr mai mare cu $x$ decât numărul celei vizitate anterior. Cu alte cuvinte, el vizitează casele cu numerele: $1, x + 1, 2 \cdot x + 1, 3 \cdot x + 1, \ldots$ și așa mai departe. Casele cu toate celelalte numere rămân nevizitate.

Pentru că vrea să fie cât mai eficient, Algorel vrea să aleagă un număr natural $x$ cât mai mare care să permită vizitarea tuturor caselor la care are de livrat colete.

Cerință

Determinați cea mai mare valoare $x$ astfel încât între casele vizitate de Algorel cu numerele $1, x + 1, 2 \cdot x + 1, 3 \cdot x + 1, \ldots$ să se regăsească toate cele $n$ case la care are de livrat colete.

Date de intrare

Fișierul de intrare posta.in conține pe prima linie numărul natural $n$, iar pe a doua linie, în ordine strict crescătoare, separate prin câte un spațiu, cele $n$ numere ale caselor de vizitat $a_1, a_2, \ldots, a_n$.

Date de ieșire

Fișierul de ieșire posta.out conține numărul natural $x$ determinat conform cerinței.

Restricții și precizări

• $2 \le n \le 10^5$;
• $1 \le a_i \le 10^{18}$ și $a_i$ este număr natural;
• $a_i < a_{i+1}$ pentru orice $i$, $1 \le i \le n - 1$.

Exemplul 1

posta.in

5
5 9 17 29 101

posta.out

4

Explicație

Dacă Algorel alege $x = 4$, atunci el vizitează casele cu numerele următoare, care includ pe toate cele $5$ la care livrează colete: $1, 5, 9, 13, 17, 21, 25, 29, \ldots, 97, 101, 105, \ldots$.

Exemplul 2

posta.in

2
7 16

posta.out

3

Explicație

Dacă Algorel alege $x = 3$, atunci el vizitează casele următoare, care includ pe cele două la care livrează colete: $1, 4, 7, 10, 13, 16, 19, \ldots$.

Exemplul 3

posta.in

3
1 5 6

posta.out

1

Explicație

Algorel trebuie să parcurgă toate casele: $1, 2, 3, 4, 5, 6, 7, \ldots$.