Инженер Яндекса Иван — очень скрупулёзный человек, из тех кто никогда не создаст массив на большее количество элементов, чем ему действительно требуется.
Сегодня у Ивана есть массив из n различных целых положительных чисел a1, a2, ..., an, который он хочет положить в хеш-таблицу. Для этого он собирается выбрать некоторое значение m — количество корзин в хеш-таблице, а затем отправить число x в корзину 
. Таким образом, число a1 попадёт в корзину h(a1), a2 попадёт в корзину h(a2) и так далее.
Настолько же сильно, насколько Иван любит порядок, он ненавидит коллизии. Поэтому он хочет выбрать значение m таким образом, чтобы все значения 
были различными. От вас требуется найти подходящее m. Поскольку эффективность во всём является одной из целей инженера, работающего с большими данными, Иван просит вас выбрать среди всех подходящих m минимальное.
В первой строке входных данных записано число n (1 ≤ n ≤ 2 000 000) — количество чисел в массиве Ивана. В следующей строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 2 000 000). Гарантируется, что все элементы последовательности a различны.
Выведите одно целое число — минимальное значение m, такое что все числа будут различными.
3
1 2 3
3
3
1 2 4
4
5
1 3 6 10 15
8
| Финал Яндекс.Алгоритм 2018 |
|---|
| Закончено |
