Divisible interval

You are given an array a of integers a[1], a[2], ..., a[n]. 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 (a[i] + a[i+1] + ... + a[j]) 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 ≤ 10^5) of elements of array a. The next line contains n integers a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 10^9).

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.

Examples

Note

a[1] + a[2] + a[3] = 4 + 2 + 4 = 10. The sum is divisible by 5.