Poștașul Algorel are de livrat colete la n case de pe Strada Progresiilor, la numerele cunoscute a1, a2, …, an. 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 numarul 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, 𝑥 + 1, 2 · 𝑥 + 1, 3 · 𝑥 + 1, … ș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ța

Determinați cea mai mare valoare x astfel încât între casele vizitate de Algorel cu numerele 1, 𝑥+1, 2·𝑥+1, 3·𝑥+1, … 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 a1, a2, …, an.

Date de ieșire

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

Restricții și precizări

• 2 ≤ n ≤ 100.000
• 1 ≤ ai ≤ 1018
• ai < ai+1, pentru orice i=1,2, ..., n-1
• pentru 65 de puncte, 2 ≤ n ≤ 200 și 1 ≤ ai ≤ 5000
• pentru 10 de puncte, 2 ≤ n ≤ 10.000 și 1 ≤ ai ≤ 1.000.000.000
• pentru 25 de puncte, fără restricții suplimentare

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: 5, 9, 17, 29, și 101

Exemplul 2:

posta.in

2
7 16

posta.out

3

Explicație

Dacă Algorel alege x = 3, atunci el vizitează casele care includ pe cele două la care livrează colete.

Exemplul 3:

posta.in

3
1 5 6

posta.out

1

Explicație

Algorel trebuie să parcurgă toate casele.