POLSKI SPOJ

Pewnego dnia, w magicznym świecie algorytmów, odbywały się prestiżowe zawody programistyczne o nazwie "Fraktal". Programiści z różnych krain przybyli, by zmierzyć się z wyzwaniem i udowodnić swoje umiejętności.

W trakcie konkurencji uczestnicy otrzymali tajemniczy ciąg liczb a₁, a₂, a₃, ..., a_n, reprezentujący pewne wyzwanie. Ich zadaniem było znaleźć maksymalną wartość wyrażenia a_i + a_j + d(a_i, a_j), gdzie d(a_i, a_j) to wartość bezwzględna różnicy indeksów tych liczb. Dopuszczano również sytuację, gdy i = j.

Podczas gdy inni programiści zagłębiali się w skomplikowane własności ciągu, Mikołaj, wykorzystując swoją wiedzę z algorytmiki, szybko zaimplementował efektywne rozwiązanie. Jego kod był jak magiczny algorytm, który odkrył ukryte piękno podanego wyzwania.

Na zakończenie zawodów, Mikołaj triumfował, zdobywając uznanie jako mistrz algorytmów. Jego historia stała się legendą w krainie programistycznych potyczek, gdzie wyzwania były niczym magiczne puzzle, a programiści szukali harmonii w chaosie kodu.

Wejście

W pierwszym wierszu jedna liczba n nie większa niż 10⁶ określająca ilość liczb w ciągu. 

W drugim wierszu n liczb naturalnych nie większych niż 10⁹.

Wyjście

Jedna liczba określająca maksymalną wartość wyrażenia podanego w treści zadania.

Przykład 1

5
1 2 4 5 3

10

Przykład 2

5
2 2 3 2 3

9