Competitions

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

# 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 data

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 data

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

Input example #1

5 4 2 4 3 6

Output example #1

1 3

## Note

`a[1]`

+ `a[2]`

+ `a[3]`

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