POLSKI SPOJ

Dany jest ciąg a o rozmiarze n składający się z liczb naturalnych.

Ciągiem serpentynowym b o rozmiarze m nazwiemy dowolny podciąg ciągu a, którego elementy spełniają poniższe równania:

• b₁ + 1 = b_m
• b_m + 1 = b₂
• b₂ + 1 = b_{m - 1}
• b_{m - 1} + 1 = b₃
• ...

Podciąg ten nie musi być spójny. Gdybyśmy narysowali linię łącząc elementy ciągu w kolejności rosnącej to utworzy nam się serpentyna zwężająca się do środka, stąd jego nazwa.

Przykładowe ciągi serpentynowe:

• 3 5 7 9 10 8 6 4
• 1 3 5 4 2
• 1000000

Odpowiedz na pytanie, jaka jest długość najdłuższego ciągu serpentynowego zawartego w ciągu a?

Wejście

W pierwszej linii wejścia znajduje się liczba n (1 ≤ n ≤ 1000000) określająca rozmiar ciągu a.

W drugiej linii znajduje się n liczb naturalnych z przedziału [1, 1000000], są to elementy ciągu a.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, jaka jest długość najdłuższego ciągu serpentynowego zawartego w ciągu a?

Przykład

Wejście:

12
9 1 3 2 5 7 8 9 10 6 4 5

Wyjście:

6

Wyjaśnienie do przykładu:

Elementy wchodzące w skład najdłuższego ciągu serpentynowego zostały wyróżnione poniżej pogrubioną czcionką:

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

Spełniają one założenia ciągu serpentynowego o rozmiarze m = 6:

• 3 (b₁) + 1 = 4 (b₆)
• 4 (b₆) + 1 = 5 (b₂)
• 5 (b₂) + 1 = 6 (b₅)
• 6 (b₅) + 1 = 7 (b₃)
• 7 (b₃) + 1 = 8 (b₄)