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

Чтобы отблагодарить Яна, Мэри подарила ему массив $$$a$$$ длины $$$n$$$. Чтобы выглядеть умным, он хочет отсортировать массив в порядке неубывания, выполнив следующее конечное число раз: он выбирает два соседних элемента $$$a_i$$$ и $$$a_{i+1}$$$ ($$$1\le i\le n-1$$$), и увеличивает оба их на $$$1$$$ или уменьшает оба их на $$$1$$$. Заметим, что элементы массива могут стать отрицательными.

Как умный человек, вы заметили, что, существуют массивы, которые Ян не сможет отсортировать в порядке неубывания! Поэтому вы решили написать программу, чтобы определить, можно ли сделать массив отсортированным в неубывающем порядке.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$2\le n\le 3\cdot10^5$$$) — количество элементов в массиве.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — элементы массива $$$a$$$.

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

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

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

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

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

В первом наборе входных данных мы можем увеличить $$$a_2$$$ и $$$a_3$$$ на $$$1$$$. Теперь массив стал $$$[1, 4, 3]$$$.

Затем мы можем уменьшить $$$a_1$$$ и $$$a_2$$$ на $$$1$$$. Теперь массив стал $$$[0, 3, 3]$$$, который отсортирован в порядке неубывания. Поэтому ответ «YES».

Во втором наборе входных данных без разницы как Ян будет применять операции, $$$a_1$$$ всегда останется больше $$$a_2$$$. Поэтому ответ «NO», и Ян не сможет показаться умным.

В третьем наборе входных данных массив уже отсортирован в порядке неубывания, поэтому Яну не нужно ничего делать.