Археологи

Ваша команда мисливців за скарбами щойно виявила величезний археологічний пам'ятник, наповнений дорогоцінними металами та цінними старовинними предметами. Пам'ятник складається з $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)$.

Вихідні дані

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

Приклади