Вам дан массив a целых чисел a[1]
, a[2]
, ..., a[n]
. Найдите любой подмассив этого массива, сумма элементов которого точно делится на n. То есть найдите такие числа (i, j) (1 ≤ i ≤ j ≤ n), что сумма (a[i]
+ a[i+1]
+ ... + a[j]
) точно делится на n. Если такая пара (i, j) не может быть найдена, то в качестве ответа выведите пару (−1, −1).
В первой строке записано количество n (1 ≤ n ≤ 10^5
) элементов массива a. В следующей строке задано n целых чисел a[1]
, a[2]
, ..., a[n]
(0 ≤ a[i]
≤ 10^9
).
Выведите любую пару (i, j) (1 ≤ i ≤ j ≤ n), удовлетворяющую условию в одной строке, или (−1, −1), если такой пары нет.
a[1]
+ a[2]
+ a[3]
= 4 + 2 + 4 = 10. Сумма делится на 5.