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

Не так давно у Влада был день рождения, на который ему подарили упаковку конфет. В ней было $$$n$$$ различных видов конфет, $$$a_i$$$ штук конфет вида $$$i$$$ ($$$1 \le i \le n$$$).

Влад решил каждый раз съедать ровно одну конфету, выбирая любую из конфет того вида, которого в текущий момент больше всего (если таких видов несколько, он может выбрать любой из них). Чтобы получить максимальное удовольствие от поедания, Влад не хочет съедать две конфеты одного вида подряд.

Помогите ему понять, может ли он съесть все конфеты, не съев две одинаковые конфеты подряд.

Входные данные

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следует описание $$$t$$$ наборов входных данных, по две строки на каждый.

Первая строка набора содержит единственное число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество видов конфет в упаковке.

Вторая строка набора содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — количество конфет вида $$$i$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите «YES», если Влад может съесть конфеты как задумывал, и «NO» в противном случае.

Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

Пример
Входные данные
6
2
2 3
1
2
5
1 6 2 4 3
4
2 2 2 1
3
1 1000000000 999999999
1
1
Выходные данные
YES
NO
NO
YES
YES
YES
Примечание

В первом примере необходимо есть конфеты в таком порядке:

  • конфету вида $$$2$$$, их больше всего, теперь $$$a = [2, 2]$$$;
  • конфету вида $$$1$$$, конфет вида $$$2$$$ столько же, но такую мы только что съели, теперь $$$a = [1, 2]$$$;
  • конфету вида $$$2$$$, их больше всего, теперь $$$a = [1, 1]$$$;
  • конфету вида $$$1$$$, теперь $$$a = [0, 1]$$$;
  • конфету вида $$$2$$$, теперь $$$a = [0, 0]$$$ и конфеты кончились.

Во втором примере все конфеты одного вида и невозможно их съесть без поедания двух одинаковых подряд.

В третьем примере в первую очередь будет съедена конфета вида $$$2$$$, после чего этот вид останется единственным видом, которого больше всего, и придётся снова съесть конфету типа $$$2$$$.