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

Мокка любит массивы, поэтому перед отъездом Базока подарил ей массив $$$a$$$, состоящий из $$$n$$$ целых положительных чисел.

Теперь Мокка хочет узнать, может ли массив $$$a$$$ стать отсортированным в порядке неубывания после выполнения следующей операции несколько (возможно, ноль) раз:

  • Разделить массив на две части — префикс и суффикс, затем поменять эти две части местами. Другими словами, пусть $$$a=x+y$$$. Тогда мы можем назначить $$$a:= y+x$$$. Здесь $$$+$$$ обозначает операцию конкатенации массивов.

Например, если $$$a=[3,1,4,1,5]$$$, мы можем выбрать $$$x=[3,1]$$$ и $$$y=[4,1,5]$$$, удовлетворяющие $$$a=x+y$$$. Тогда мы можем назначить $$$a:= y + x = [4,1,5,3,1]$$$. Также для начального массива мы можем выбрать $$$x=[3,1,4,1,5]$$$ и $$$y=[\,]$$$, удовлетворяющие $$$a=x+y$$$. Тогда мы можем назначить $$$a := y+x = [3,1,4,1,5]$$$. Заметим, что мы не можем выбрать $$$x=[3,1,1]$$$ и $$$y=[4,5]$$$, а также $$$x=[1,3]$$$ и $$$y=[5,1,4]$$$, так как оба эти варианта не удовлетворяют $$$a=x+y$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\leq n\leq 50$$$) — длину массива $$$a$$$.

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

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

Для каждого набора входных данных выведите «Yes», если массив $$$a$$$ может стать неубывающим после выполнения операции любое количество раз, и «No», если не может.

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

Пример
Входные данные
3
6
1 1 4 5 1 4
5
7 9 2 2 3
3
1 2 3
Выходные данные
No
Yes
Yes
Примечание

Для первого набора входных данных можно доказать, что массив $$$a$$$ не может стать неубывающим после выполнения операции любое количество раз.

Во втором наборе входных данных мы можем выполнить следующие операции, чтобы сделать $$$a$$$ отсортированным в неубывающем порядке:

  • Разделить массив на две части: $$$x=[7]$$$ и $$$y=[9,2,2,3]$$$, затем поменять эти две части местами. Массив станет равен $$$y+x = [9,2,2,3,7]$$$.
  • Разделить массив на две части: $$$x=[9]$$$ и $$$y=[2,2,3,7]$$$, затем поменять местами эти две части. Массив станет равен $$$y+x=[2,2,3,7,9]$$$, то есть станет неубывающим.