eolymp
Competitions

2022 Azerbaijan Round 1, 8-9-10-11 classes

Divisible interval

You are given an array a of integers a1, a2, ..., an. Find any subarray of this array which sum of elements is exactly divisible by n. That is, find numbers (i, j) (1ijn) such that the sum (ai + ai+1 + ... + aj) is exactly divisible by n. If such a pair (i, j) cannot be found, then output the pair (−1, −1) as an answer.

Input

The first line contains the number n (1n105) of elements of array a. The next line contains n integers a1, a2, ..., an (0ai109).

Output

Print any pair (i, j) (1ijn) satisfying the condition in one line, or (−1, −1) if there is no such pair.

Explanation

a1 + a2 + a3 = 4 + 2 + 4 = 10. The sum is divisible by 5.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5
4 2 4 3 6
Output example #1
1 3
Source 2022 Azerbaijan Round 1, 10-11 classes