A. Экстремальное вычитание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ положительных чисел.

Вы можете применять следующую операцию, сколько угодно раз: выбрать любое целое число $$$1 \le k \le n$$$ и выполнить одно из двух действий:

  • отнять от $$$k$$$ первых элементов массива единицу.
  • отнять от $$$k$$$ последних элементов массива единицу.

Например, если $$$n=5$$$ и $$$a=[3,2,2,1,4]$$$, то вы можете применить к нему одну из следующих операций (ниже перечислены не все возможные варианты):

  • отнять от первых двух элементов массива единицу. После этой операции $$$a=[2, 1, 2, 1, 4]$$$;
  • отнять от трех последних элементов массива единицу. После этой операции $$$a=[3, 2, 1, 0, 3]$$$;
  • отнять от пяти первых элементов массива единицу. После этой операции $$$a=[2, 1, 1, 0, 3]$$$;

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

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

В первой строке находится одно целое положительное число $$$t$$$ ($$$1 \le t \le 30000$$$) — количество наборов тестовых данных. Далее следуют $$$t$$$ наборов тестовых данных.

Каждый набор начинается со строки в которой записано одно целое число $$$n$$$ ($$$1 \le n \le 30000$$$) — количество элементов в массиве.

Во второй строке каждого набора тестовых данных записаны $$$n$$$ целых чисел $$$a_1 \ldots a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Сумма $$$n$$$ по всем наборам тестовых данных не превосходит $$$30000$$$.

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

Для каждого набора тестовых данных в отдельной строке выведите:

  • YES, если возможно сделать все элементы массива равными нулю применив некоторое количество операций.
  • NO, иначе.

Буквы в словах YES и NO можно выводить в любом регистре.

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