Вы являетесь тренером группы из \(n\) студентов. Умение программировать \(i\)-го студента равно числу \(a_i\). Умения программировать всех студентов различны. Вы хотите поделить их на команды таким образом, что:
- Не существует двух студентов \(i\) и \(j\), принадлежащих одной команде, таких, что \(|a_i - a_j| = 1\) (т.е. разница между умениями программировать в каждой паре студентов из одной команды должна быть строго больше, чем \(1\));
- число команд минимально возможное.
Вы должны ответить на \(q\) независимых запросов.
Выходные данные
Для каждого запроса выведите ответ на него — минимальное количество команд, которые вы можете составить, если никакие два студента \(i\) и \(j\) такие, что \(|a_i - a_j| = 1\), не принадлежат одной команде (т.е. умения программировать в каждой паре студентов из одной команды различаются строго больше, чем на \(1\))
Примечание
В первом запросе тестового примера \(n=4\) студента с умениями программировать \(a=[2, 10, 1, 20]\). Здесь есть только одно ограничение: \(1\)-й и \(3\)-й студенты не могут быть в одной команде (потому что \(|a_1 - a_3|=|2-1|=1\)). Можно разделить их на \(2\) команды: например, студенты \(1\), \(2\) и \(4\) в первой команде и студент \(3\) во второй команде.
Во втором запросе тестового примера \(n=2\) студента с умениями программировать \(a=[3, 6]\). Можно составить единственную команду, в которую входят оба студента.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
2 10 1 20
2
3 6
5
2 3 4 99 100
1
42
|
2
1
2
1
|