Районная олимпиада по информатике 2022 года за 10 класс | Казахстанские олимпиады

Задача C. Алихан и массив

Есть массив $a$ состоящий из $n$ целых чисел. Алихан хочет ко всем числам массива прибавить неотрицательное целое число $x$ так, чтобы после этого ни одно из чисел не делилось(без остатка) на $n$. Найдите минимальный такой $x$.

Формат входного файла

В первой строке находится одно целое число $n(1 \leq n \leq 10^5)$.

Во второй строке находятся $n$ целых числа $a_1, a_2, ..., a_n(1 \leq a_i \leq n)$.

Формат выходного файла

Если не существует такого числа $x$, выведите $−1$.

Иначе, выведите число $x$.

Примеры

Ввод

5
1 3 2 1 4

Вывод

0

Ввод

4
4 1 3 1

Вывод

2