Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_AA_11 - Ciąg serpentynowy

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:

  • b1 + 1 = bm
  • bm + 1 = b2
  • b2 + 1 = bm - 1
  • bm - 1 + 1 = b3
  • ...

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 (b1) + 1 = 4 (b6)
  • 4 (b6) + 1 = 5 (b2)
  • 5 (b2) + 1 = 6 (b5)
  • 6 (b5) + 1 = 7 (b3)
  • 7 (b3) + 1 = 8 (b4)

Dodane przez:Maciej Boniecki
Data dodania:2021-04-19
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.