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.