Вы являетесь тренером группы из $$$n$$$ студентов. Умение программировать $$$i$$$-го студента равно числу $$$a_i$$$. Умения программировать всех студентов различны. Вы хотите поделить их на команды таким образом, что:
Вы должны ответить на $$$q$$$ независимых запросов.
Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 100$$$) — количество запросов. Затем следуют $$$q$$$ запросов.
Первая строка запроса содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество студентов в запросе. Вторая строка запроса содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$, все $$$a_i$$$ различны), где $$$a_i$$$ — умение программировать $$$i$$$-го студента.
Для каждого запроса выведите ответ на него — минимальное количество команд, которые вы можете составить, если никакие два студента $$$i$$$ и $$$j$$$ такие, что $$$|a_i - a_j| = 1$$$, не принадлежат одной команде (т.е. умения программировать в каждой паре студентов из одной команды различаются строго больше, чем на $$$1$$$)
4 4 2 10 1 20 2 3 6 5 2 3 4 99 100 1 42
2 1 2 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]$$$. Можно составить единственную команду, в которую входят оба студента.
| Codeforces Round 595 (Div. 3) |
|---|
| Закончено |
