@NikPro34677

Помогите решить задачу



ограничение по времени на тест 1 секунда
ограничение по памяти на тест 256 мегабайт
ввод стандартный ввод
вывод стандартный вывод

Вам дан массив a, состоящий из n положительных (больших нуля) целых чисел.

За один ход вы можете выбрать два индекса i и j (i≠j) таких, что абсолютная разность между ai и aj не превосходит единицу (|ai−aj|≤1), и удалить наименьший из этих двух элементов. Если два элемента равны, вы можете удалить любой из них (но только один).

Ваша задача — определить, возможно ли получить массив, состоящий только из одного элемента, применив несколько (возможно, ноль) таких ходов, или нет.

Вам нужно ответить на t независимых наборов тестовых данных.

Входные данные
Первая строка теста содержит одно целое число t (1≤t≤1000) — количество наборов тестовых данных. Затем следуют t наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число n (1≤n≤50) — длину a. Вторая строка набора тестовых данных содержит n целых чисел a1,a2,…,an (1≤ai≤100), где ai — i-й элемент a.

Выходные данные
Для каждого набора тестовых данных выведите ответ на него: «YES», если возможно получить массив, состоящий только из одного элемента, применив несколько (возможно, ноль) ходов, описанных в условии задачи, или «NO» в обратном случае.

ВХОДНЫЕ ДАННЫЕ:
5
3
1 2 2
4
5 5 5 5
3
1 2 4
4
1 3 4 4
1
100

ВЫХОДНЫЕ ДАННЫЕ:
YES
YES
NO
NO
YES

Примечание
В первом наборе тестовых данных примера мы можем применить следующую последовательность ходов:

выбрать i=1 и j=3, а затем удалить ai (таким образом, a превратится в [2;2]);
выбрать i=1 и j=2, а затем удалить aj (таким образом, a превратится в [2]).
Во втором наборе тестовых данных примера мы можем выбирать любые возможные i и j в течение любого хода и удалять любой элемент из пары.

В третьем наборе тестовых данных примера не существует способа избавиться от 2 и 4.

0

@Jorka

хмм, это бан думаю

0

@AlexVRud

1. отсортировать массив чисел по возрастанию;
2. посчитать количество событий a[i+1]-a[i]>1
3. если таких событий 0 то YES, иначе NO;

Сортировать мы можем, т.к. можем выбирать любые индексы.
А любая отсортированная последовательность, где соседние элементы отличаются не больше чем на 1, элементарно превращается в одно число.

0