Problem description

Back
Show PDF
Krasnalowe NWD
(M)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

Krasnal Bitek ma tablicę długości N. Niedawno poznał pojęcie największego wspólnego dzielnika (NWD). NWD tablicy to największa liczba całkowita d taka, że każdy element tablicy jest podzielny przez d. Bitek bardzo by chciał, żeby NWD jego tablicy był jak największy.

Bitek znalazł ostatnio magiczną różdżkę, która pozwala mu wykonać dowolną liczbę operacji (w szczególności można nie wykonać żadnej). W jednej operacji Bitek wybiera indeks i (1 ≤ i ≤ N) oraz dowolną liczbę całkowitą dodatnią x, a następnie zamienia Ai na Ai mod  x, czyli na resztę z dzielenia Ai przez x.

Ponieważ Bitek bardzo boi się zer, w tablicy w żadnym momencie nie może pojawić się liczba 0. Pomóż Bitkowi obliczyć maksymalny możliwy NWD tablicy, jaki da się uzyskać po wykonaniu kilku (być może żadnych) operacji.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą N.

Drugi wiersz wejścia zawiera N liczb całkowitych A1, A2, …, AN, oddzielonych pojedynczym odstępem, oznaczających kolejne elementy tablicy Bitka.

Wyjście

Wypisz jedną liczbę całkowitą – maksymalny możliwy NWD tablicy po wykonaniu kilku (być może żadnych) operacji.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ Ai ≤ 109.

Przykłady

Wejście Wyjście Wyjaśnienie 
3
3 9 11

3

Można na przykład wybrać indeks i = 3 (wskazujący na element o wartości 11) oraz x = 4, a następnie zamienić 11 na 11 mod  4 = 3. Otrzymujemy tablicę [3,9,3] o NWD równym 3. Da się pokazać, że lepszego wyniku osiągnąć nie można.
Wejście Wyjście Wyjaśnienie 
4
6 12 18 24

6

Tablica ma już NWD równe 6, więc nie musimy wykonywać żadnej operacji.
Wejście Wyjście Wyjaśnienie 
2
4 7

2

Możemy wybrać indeks i = 2 (element o wartości 7) oraz x = 5 i zamienić 7 na 7 mod  5 = 2. Otrzymujemy tablicę [4,2] o NWD równym 2.