Odległość

Limit pamięci: 32 MB

Mamy daną tablicę liczb całkowitych. Chcielibyśmy znaleźć w tej tablicy takie dwa elementy i , aby zmaksymalizować wartość , gdzie to odległość między tymi liczbami. Elementy nie muszą być różne, a odległość pomiędzy tym samym elementem wynosi .

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę elementów w tablicy. Drugi wiersz wejścia zawiera liczb całkowitych (), gdzie oznacza -ty element w tablicy.

W testach wartych około puktów zachodzi dodatkowy warunek .

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą maksymalnej wartości .

Przykład

Dla danych wejściowych:

5
2 5 4 7 3

poprawną odpowiedzią jest:

14

Autor zadania: Jacek Tomasiewicz.