Мокка любит массивы, поэтому перед отъездом Базока подарил ей массив \(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\).
Выходные данные
Для каждого набора входных данных выведите «Yes», если массив \(a\) может стать неубывающим после выполнения операции любое количество раз, и «No», если не может.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «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]\), то есть станет неубывающим.