Вам дан массив \(a\) из \(n\) целых положительных чисел и целое число \(x\). Вы можете выполнить следующую двухшаговую операцию любое число раз (возможно, ноль):
- Выбрать индекс \(i\) (\(1 \leq i \leq n\)).
- Увеличить \(a_i\) на \(x\) (другими словами, \(a_i := a_i + x\)).
Найдите максимальное значение \(\operatorname{MEX}\) массива \(a\) при оптимальном выполнении операций.
\(\operatorname{MEX}\) (минимальное исключенное) массива — это наименьшее целое неотрицательное число, которого нет в массиве. Например:
- \(\operatorname{MEX}\) массива \([2,2,1]\) равен \(0\), потому что \(0\) нет в массиве.
- \(\operatorname{MEX}\) массива \([3,1,0,1]\) равен \(2\), потому что \(0\) и \(1\) есть в массиве, а \(2\) — нет.
- \(\operatorname{MEX}\) массива \([0,3,1,2]\) равен \(4\), потому что \(0\), \(1\), \(2\) и \(3\) есть в массиве, а \(4\) — нет.
Выходные данные
Для каждого набора входных данных выведите одно целое число: максимальный \(\operatorname{MEX}\) массива \(a\) при оптимальном выполнении операций.
Примечание
В первом наборе входных данных \(\operatorname{MEX}\) массива \(a\) равен \(4\) без выполнения каких-либо операций, что является максимумом.
Во втором наборе входных данных \(\operatorname{MEX}\) массива \(a\) равен \(5\) без выполнения каких-либо операций. Если мы выполним две операции, обе с \(i=1\), то получим массив \(a=[5,3,4,1,0,2]\). Тогда \(\operatorname{MEX}\) массива \(a\) станет \(6\), что является максимумом.
В третьем наборе входных данных \(\operatorname{MEX}\) массива \(a\) без выполнения каких-либо операций равен \(0\), что является максимумом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 3
0 3 2 1 5 2
6 2
1 3 4 1 0 2
4 5
2 5 10 3
|
4
6
0
|