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

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

  • Если в автобусе нет занятых мест, пассажир может сесть на любое свободное место;
  • Иначе пассажиру следует сесть на любое свободное место, рядом с которым есть занятое место. Другими словами, пассажир должен садиться на место с индексом $$$i$$$ ($$$1 \le i \le n$$$), только если существует хотя бы одно из мест с индексами $$$i-1$$$ или $$$i+1$$$, и при этом хотя бы одно из этих мест занято.

Сегодня в автобус зашли $$$n$$$ пассажиров. В массиве $$$a$$$ в хронологическом порядке записаны номера мест, на которые они садились. То есть, $$$a_1$$$ содержит номер места, на которое сел первый пассажир, $$$a_2$$$ — номер места, на которое сел второй пассажир, и так далее.

Вам известно содержимое массива $$$a$$$. Определите, все ли пассажиры соблюдали рекомендации.

Например, если $$$n = 5$$$ и $$$a$$$= [$$$5, 4, 2, 1, 3$$$], то рекомендации не были соблюдены, так как $$$3$$$-й пассажир сел на место с номером $$$2$$$, в то время как соседние места с номерами $$$1$$$ и $$$3$$$ были свободны.

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

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

Далее следуют описания наборов входных данных.

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

Вторая строка каждого набора содержит $$$n$$$ различных чисел $$$a_i$$$ ($$$1 \le a_i \le n$$$) — места, на которые садились пассажиры в хронологическом порядке.

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

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

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

  • «YES», если все пассажиры соблюдали рекомендации;
  • «NO» иначе.

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

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

Первый набор входных данных разобран в условии задачи.