Не так давно у Влада был день рождения, на который ему подарили упаковку конфет. В ней было \(n\) различных видов конфет, \(a_i\) штук конфет вида \(i\) (\(1 \le i \le n\)).
Влад решил каждый раз съедать ровно одну конфету, выбирая любую из конфет того вида, которого в текущий момент больше всего (если таких видов несколько, он может выбрать любой из них). Чтобы получить максимальное удовольствие от поедания, Влад не хочет съедать две конфеты одного вида подряд.
Помогите ему понять, может ли он съесть все конфеты, не съев две одинаковые конфеты подряд.
Выходные данные
Выведите \(t\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите «YES», если Влад может съесть конфеты как задумывал, и «NO» в противном случае.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|