Codeforces Round 947 (Div. 1 + Div. 2) |
---|
Закончено |
Мокка любит массивы, поэтому перед отъездом Базока подарил ей массив $$$a$$$, состоящий из $$$n$$$ целых положительных чисел.
Теперь Мокка хочет узнать, может ли массив $$$a$$$ стать отсортированным в порядке неубывания после выполнения следующей операции несколько (возможно, ноль) раз:
Например, если $$$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» будут приняты как положительный ответ.
361 1 4 5 1 457 9 2 2 331 2 3
No Yes Yes
Для первого набора входных данных можно доказать, что массив $$$a$$$ не может стать неубывающим после выполнения операции любое количество раз.
Во втором наборе входных данных мы можем выполнить следующие операции, чтобы сделать $$$a$$$ отсортированным в неубывающем порядке:
Название |
---|