Processing math: 100%

Задача E. Мёд и справедливость

Автор:Кленин А. С.   Ограничение времени:4 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит ai микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M+1 до R включительно (LM<R). Чтобы ни одной из пчёл не обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

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

Входные данные содержат целое число N, за которым следует N чисел ai.

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

Выходные данные должны содержать целые числа LMR — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число 1.

Ограничения

2N10000

1ai105

Примеры тестов

Стандартный вход Стандартный выход
1
3
1 1 2
1 2 3
2
2
2 5
-1

0.053s 0.007s 13