Wstęp do programowania w C++

Bajtek zapisał na tablicy ciąg liczb naturalnych. Chciał, żeby był to ciąg ściśle rosnący, czyli żeby każdy wyraz był większy od poprzednich, ale z przerażeniem odkrył, że być może mu się to nie udało. Postanowił więc wybrać liczbę naturalną dodatnią K, nie większą od miliona, i usunąć z ciągu wszystkie liczby niepodzielne przez K.

Przykładowo, jeżeli ciąg zapisany przez Bajtka to (1, 5, 8, 10, 7, 25, 14) i Bajtek wybierze liczbę K = 5, to uzyska ciąg (5, 10, 25). Taki ciąg jest rosnący, co satysfakcjonuje go niezmiernie.

Bajtek chciałby tak wybrać wartość K, żeby ciąg był ściśle rosnący, a liczba pozostawionych elementów w ciągu była jak największa. Jeżeli nie da się inaczej, Bajtek zgodzi się na usunięcie wszystkich liczb z tablicy, czyli pustą tablicę również potraktuje jako ciąg ściśle rosnący.

Input

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N (1 ≤ N ≤ 1 000 000) określająca długość ciągu zapisanego przez Bajtka. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych A_i (1 ≤ A_i ≤ 1 000 000) pooddzielanych pojedynczymi odstępami. Są to kolejne liczby zapisane przez Bajtka.

Output

W pierwszym (i jedynym) wierszu wyjścia powinna znaleźć się jedna liczba naturalna dodatnia nie większa niż 1 000 000 – liczba K, którą powinien wybrać Bajtek. Jeżeli istnieje wiele możliwych odpowiedzi, Twój program może wypisać dowolną z nich.

Scoring

Możesz rozwiązać zadanie w kilku prostszych wariantach – niektóre grupy testów spełniają pewne dodatkowe ograniczenia. Poniższa tabela pokazuje, ile punktów otrzyma Twój program, jeżeli przejdzie testy z takim ograniczeniem.

Example

Input:
7
1 5 8 10 7 25 14

Output:
5

Input:
10
1 2 3 4 5 6 7 8 9 10

Output:
1