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) (1 ≤ i ≤ j ≤ n) 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 (1 ≤ n ≤ 105) of elements of array a. The next line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109).

Output

Print any pair (i, j) (1 ≤ i ≤ j ≤ n) 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.