Ваша команда охотников за сокровищами только что обнаружила гигантский археологический объект, полный драгоценных металлов и ценных древностей. Объект состоит из $n$ мест для раскопок, расположенных на одной линии.

Первоначальные планы предполагают, что каждое из $n$ мест имеет связанную с ним чистую прибыль. Для $i$-го места эта прибыль равна $p_i$. Это означает, что ваша команда получит $p_i$ долларов за каждый метр, выкопанный в $i$-м месте. Заметим, что $p_i$ может быть отрицательным, что означает, что эксплуатационные расходы на землеройную технику превышают фактическую прибыль от раскопок в $i$-м месте.

Естественно, вы хотите копать как можно больше в наиболее прибыльных местах. Однако, чтобы не вызвать оползни, вам не разрешается делать слишком крутые склоны. Точнее, для любых двух соседних мест разница между глубиной раскопок в этих местах не может превышать 1 метр. В частности, места $1$ и $n$ можно копать на глубину не более 1 метра.

Какую наибольшую чистую прибыль вы можете получить при таких условиях?

Например, допустимый план раскопок, который оказывается оптимальным в случае первого примера, проиллюстрирован ниже. Чистая прибыль такого плана равна 8.

Входные данные

Первая строка входных данных содержит целое положительное число $n$ ($1 \le n \le 250\,000$).

Вторая строка входных данных содержит $n$ целых чисел $p_i$ ($-10^6 \le p_i \le 10^6$), разделенных пробелами.

Выходные данные

Выведите ровно одно целое число — наибольшую прибыль, которую вы можете получить.

Примеры

Входные данные 1

5
1 3 -4 2 1

Выходные данные 1

8

Входные данные 2

4
1 1 -2 3

Выходные данные 2

5

Входные данные 3

5
-1 -3 0 -5 -4

Выходные данные 3

0