Женя совсем не любит работать, однако ему очень нравится чай Да Хун Пао, который известен своим релаксирующим эффектом. На очередной чайной сессии с Да Хун Пао Евгений задался вопросом, как он может максимизировать своё суммарное расслабление.
На сессии ему предлагается $$$n$$$ чашек с любимым чаем различных сортов, каждая из которых имеет свой коэффициент расслабления $$$a_i$$$. Чашки с чаем стоят в ряд, без пропусков, на одинаковом расстоянии друг от друга. Чтобы не нарушать эстетику, которой Женя очень дорожит, он действует так: пока на столе ещё остались чашки, выбирает либо самую левую, либо самую правую чашку, и выпивает весь чай из неё. После этого сервировщик убирает чашку со стола.
От первой выпитой в течение сессии чашки Женя расслабляется на $$$x_1$$$ единиц, где $$$x_1$$$ — это коэффициент расслабления для первой выпитой чашки чая. От следующей — на $$$2 x_2$$$ единиц, где $$$x_2$$$ — это коэффициент расслабления для второй выпитой чашки чая. И так далее: от чашки, выпитой под номером $$$i$$$, Евгений расслабляется на $$$i x_i$$$ единиц.
Помогите Жене узнать, какое максимальное суммарное количество единиц расслабления он сможет получить за сессию с Да Хун Пао.
В первой строке задано целое число $$$n$$$ ($$$1 \le n \le 5000$$$).
В следующей строке записано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — коэффициенты расслабления всех предоставленных Жене чашек Да Хун Пао.
Выведите одно целое число: максимальную суммарную величину расслабления, которой Женя может достичь в течение сессии Да Хун Пао.
41 2 3 4
30
41 2 1 1
14
