Вам дан массив различных целых положительных чисел \(a_1, a_2, \dots, a_n\). Вы должны выполнить следующую операцию ровно один раз:
- выбрать целое положительное число \(k\);
- для каждого \(i\) от \(1\) до \(n\) заменить \(a_i\) на \(a_i \text{ mod } k^\dagger\).
Найдите такое значение \(k\), такое что \(1 \leq k \leq 10^{18}\), чтобы массив \(a_1, a_2, \dots, a_n\) содержал ровно \(2\) различных значения после применения операции. Можно показать, что при ограничениях задачи хотя бы одно такое \(k\) всегда существует. Если существует несколько решений, выведите любое из них.
\(^\dagger\) \(a \text{ mod } b\) обозначает остаток от деления \(a\) на \(b\). Например:
- \(7 \text{ mod } 3=1\), так как \(7 = 3 \cdot 2 + 1\)
- \(15 \text{ mod } 4=3\), так как \(15 = 4 \cdot 3 + 3\)
- \(21 \text{ mod } 1=0\), так как \(21 = 21 \cdot 1 + 0\)
Выходные данные
Для каждого набора входных данных выведите одно целое число: значение \(k\) (\(1 \leq k \leq 10^{18}\)) такое, что массив \(a_1, a_2, \dots, a_n\) будет содержать ровно \(2\) различных значения после применения операции.
Примечание
В первом наборе входных данных можно выбрать \(k = 7\). Массив станет равным \([8 \text{ mod } 7, 15 \text{ mod } 7, 22 \text{ mod } 7, 30 \text{ mod } 7] = [1, 1, 1, 2]\) и будет содержать ровно \(2\) различных значения (\(\{1, 2\}\)).
Во втором наборе входных данных можно выбрать \(k = 30\). Массив станет равным \([0, 0, 8, 0, 8]\), то есть будет содержать ровно \(2\) различных значения (\(\{0, 8\}\)). Заметим, что выбор \(k = 10\) также будет корректным решением.
В последнем наборе входных данных можно выбрать \(k = 10^{18}\). Массив станет равным \([2, 1]\) и будет содержать ровно \(2\) различных значения (\(\{1, 2\}\)). Заметим, что выбор \(k = 10^{18} + 1\) не будет корректным, так как должно выполняться \(1 \leq k \leq 10^{18}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
8 15 22 30
5
60 90 98 120 308
6
328 769 541 986 215 734
5
1000 2000 7000 11000 16000
2
2 1
|
7
30
3
5000
1000000000000000000
|