СРОЧНО ПОМОГИТЕ НАПИСАТЬ ПРОГРАММУ. ОЛИМПИАДА ПО ИНФОРМАТИКЕ

При проектировании новой автодороги было принято решение сделать её не более чем из двух абсолютно горизонтальных участков. Будущую трассу разбили на nn равных по длине малых отрезков. Будем считать, что в пределах одного малого отрезка местность имеет одну и ту же высоту h_ih
i
​
. При этом в целях эффективной трансформации местности требуется для выравнивания использовать исключительно грунт с этой же трассы. Это означает, что можно с некоторого малого отрезка высоты h_ih
i
​
взять некоторое количество грунта dd так, что высота этого участка станет h_i - d > 0h
i
​
−d>0. Далее эти dd единиц грунта обязательно нужно переместить на другой малый отрезок высоты h_jh
j
​
так, что его высота станет h_j + dh
j
​
+d. Перемещать грунт можно только в пределах одного из двух выбранных участков, то есть отрезки номер ii и номер jj должны принадлежать одному и тому же горизонтальному после выравнивания участку. В данной версии задачи высоты выравниваемых участков могут быть любыми положительными, в том числе и не целыми числами. Следующим важным вопросом при строительстве являются трудозатраты. По этой причине требуется выбрать такое разбиение трассы ровно на два непустых участка, чтобы суммарный объём перемещенного грунта был минимально возможным.

Формат входных данных

В первой строке содержится число nn - количество малых отрезков, на которые разбили трассу, 2 \leq n \leq 2*10^52≤n≤2∗10
5
. Во второй строке указаны высоты h_ih
i
​
этих отрезков через пробел в порядке слева направо, 1 \leq h_i \leq 2*10^51≤h
i
​
≤2∗10
5
.

Формат выходных данных

Вывести два ненулевых числа aa и bb через пробел. Их сумма должна равняться nn. Отрезки с номерами c первого по aa-й включительно будут принадлежать первому выровненному участку, отрезки с номерами от a+1a+1 до nn будут принадлежать второму выровненному участку. При этом суммарный объём грунта, перемещенного для такого выравнивания, должен быть минимальным среди всех возможных разбиений трассы на два участка. Если минимальных вариантов несколько вывести тот, у которого число aa меньше.

Пояснение к примеру.

На следующих рисунках приведены рассуждения для трёх вариантов разбиения трассы на два участка,

a = 3, b = 5:
a = 6, b = 2:
a = 4, b = 4:

Если перебрать все варианты разбиения трассы на две части, самым оптимальным будет разбиение 4 4 с результатом 12.5

Sample Input:

8
8 20 2 10 4 3 1 1
Sample Output:

4 4