5. Тайна священной последовательности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Жрецы тайного ордена выстроились в очередь, чтобы поклониться древнему богу. Каждый принёс с собой дар — целое положительное число, высеченное на камне.

По преданию, ритуал считается завершённым, если выбрать подряд идущих жрецов (не пустую группу; группа может состоять из одного жреца) так, чтобы сумма их даров делилась на общее количество жрецов $$$n$$$.

Определите, можно ли найти такую группу. Если такой группы нет, выведите $$$-1$$$. Если она существует, укажите её начало и конец.

Входные данные

Первая строка: одно целое число $$$n$$$ ($$$1 \leq n \leq 10^{5}$$$) — количество жрецов.

Вторая строка: последовательность из $$$n$$$ целых положительных чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

Обратите внимание, что значение промежуточных вычислений может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Выходные данные

Если подходящей группы жрецов не существует, выведите $$$-1$$$.

Если группа существует, выведите два целых числа: $$$l, r \ (1 \leq l \leq r \leq n)$$$  — номера первого и последнего жреца в очереди, образующих непрерывную подпоследовательность, сумма в которой делится на $$$n$$$. Если решений несколько, можно вывести любое.

Система оценки

Решения, правильно работающие при $$$n \leq 100$$$, будут оцениваться в $$$20$$$ баллов.

Решения, правильно работающие при $$$n \leq 1000$$$, будут оцениваться в $$$40$$$ баллов.

Примеры
Входные данные
3
1 1 1
Выходные данные
1 3
Входные данные
5
2 3 2 3 1
Выходные данные
1 2
Примечание

В первом тесте сумма всех трёх единиц равна 3, что делится на 3.

Во втором тесте сумма первых двух чисел $$$2+3=5$$$, что делится на 5. При этом также подходит и сумма первых четырёх чисел, сумма второго и третьего числа или сумма третьего и четвёртого.