Археологи

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

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

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

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

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

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

Первая строка содержит натуральное число $n(1\le n\le 250000)$.

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

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

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

Примеры