시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Задан массив натуральных чисел [a1, a2, . . . , an]. Весом массива назовём сумму его элементов.

Необходимо разрезать заданный массив на два непустых массива [a1, a2, . . . , ai] и [ai+1, ai+2, . . . , an] так, чтобы произведение их весов было как можно больше.

Требуется написать программу, которая по заданному массиву определяет, после какого элемента его необходимо разрезать, чтобы произведение весов получившихся массивов было максимальным.

입력

В первой строке входных данных находится целое число n — количество элементов в массиве (2 ≤ n ≤ 2 · 105). В следующей строке находятся n целых чисел a1, a2, . . . , an — элементы массива (1 ≤ ai ≤ 109).

출력

Выведите одно число — номер элемента, после которого необходимо разрезать заданный массив. Если оптимальных вариантов ответа несколько, можно вывести любой из них.

서브태스크

번호 배점 조건
1 10

2 ≤ n ≤ 5000

Сумма всех ai не превосходит 109

2 10

2 ≤ n ≤ 5000

Все ai равны

3 20

2 ≤ n ≤ 5000

ai ≤ 109

4 20

2 ≤ n ≤ 200000

Сумма всех ai не превосходит 109

5 20

2 ≤ n ≤ 200000

Все ai равны

6 20

2 ≤ n ≤ 200000

ai ≤ 109

예제 입력 1

3
1 2 3

예제 출력 1

2

힌트

Если сделать разрез после первого элемента, произведение весов равно 1 · (2 + 3) = 5, а если после второго, то (1 + 2) · 3 = 9.

채점 및 기타 정보

  • 예제는 채점하지 않는다.