У Васи есть два хобби — прибавлять перестановки\(^{\dagger}\) к массивам и находить самый часто встречающийся элемент. Недавно он нашел массив \(a\) и решил узнать, какое максимальное количество элементов равных одинаковому числу в массиве \(a\) он может получить после того, как прибавит какую-то перестановку к массиву \(a\).
Более формально, Вася может выбрать какую-то перестановку \(p_1, p_2, p_3, \ldots, p_n\) длины \(n\), после чего изменить элементы массива \(a\) по правилу \(a_i := a_i + p_i\). После этого Вася считает, сколько раз каждое число встречается в массиве \(a\), и берёт максимум по этим значениям. Вам нужно определить, какое максимальное значение он может получить.
\(^{\dagger}\)Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите одно число — максимальное количество элементов, равных одинаковому числу, после операции прибавления перестановки.
Примечание
В первом наборе входных данных оптимально выбрать \(p = [2, 1]\). Тогда после применения операции массив \(a\) будет равен \([3, 3]\), в котором число \(3\) встречается дважды, поэтому ответ равен \(2\).
Во втором наборе входных данных одним из оптимальных вариантов является \(p = [2, 3, 1, 4]\). После применения операции массив \(a\) будет равен \([9, 4, 5, 5]\). Так как число \(5\) встречается дважды, то ответ равен \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2
1 2
4
7 1 4 1
3
103 102 104
5
1 101 1 100 1
5
1 10 100 1000 1
2
3 1
3
1000000000 999999997 999999999
|
2
2
3
2
1
1
2
|