Наступает конечный этап проекта Манхеттен, поэтому Роберт Оппенгеймер планирует перевести всех сотрудников в одну команду для проверки расчетов и финальных приготовлений. Сейчас сотрудники работают в здании, в котором есть $$$n$$$ больших залов с аппаратурой для исследований. В зале $$$i$$$ находится ровно $$$a_i$$$ сотрудников. При этом в здании залы стоят в линию, поэтому за раз сотрудник может перейти лишь в соседний по номеру зал.
Оппенгеймер понимает, что каждому работнику для работы требуется его оборудование, поэтому нельзя просто взять и привести всех в один зал: перевод сотрудника сопровождается переносом всего его оборудования, что довольно накладно и требует времени, которое можно было тратить на исследования. Поэтому начальство хочет сделать объединение команд наименее накладным. Сложность объединения считается как количество переходов сотрудников из своих залов в соседние по пути в зал, где они все по итогу будут работать.
Помогите найти минимальную возможную сложность процесса объединения. Высшее командование заранее выражает вам благодарность за сотрудничество.
В первой строке ввода дано целое число $$$n$$$ — количество залов в здании проекта Манхэттен ($$$1 \le n \le 2 \cdot 10^5$$$).
В следующей строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — количество сотрудников в зале $$$i$$$ ($$$1 \le a_i \le 10^9$$$).
Выведите одно число — минимальную сложность перевода всех сотрудников в один и тот же зал.
41 3 2 5
10
51 2 3 4 5
15