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

Дана последовательность $$$a$$$, состоящая из $$$n$$$ положительных целых чисел.

Вы можете выполнять следующую операцию любое количество раз.

  • Выберите индекс $$$i$$$ ($$$1 \le i < n$$$) и вычтите $$$\min(a_i,a_{i+1})$$$ из обоих $$$a_i$$$ и $$$a_{i+1}$$$.

Определите, возможно ли сделать последовательность неубывающей, используя операцию любое количество раз.

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Описание наборов входных данных следует далее.

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

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

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

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

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

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

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

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

Во втором наборе входных данных можно показать, что это невозможно.

В третьем наборе входных данных, после выполнения операции на $$$i=1$$$, массив становится $$$[0,1,2,3]$$$, который теперь находится в неубывающем порядке.