← 返回题目列表

Codeforces · 1975/A

A. 火箭筒和摩卡的阵列

中文机器翻译题面 查看原题

Mocha喜欢数组,所以在她出发之前,Bazoka送给她一个由$$$n$$$正整数组成的数组$$$a$$$作为礼物。

现在 Mocha 想知道数组 $$$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$$$ 的元素。

输出

对于每个测试用例,如果 $$$a$$$ 在执行任意次操作后可以变为非递减,则输出“Yes”,否则输出“No”。

在任何情况下都可以输出“Yes”和“No”(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应)。

示例

输入 #1

3
6
1 1 4 5 1 4
5
7 9 2 2 3
3
1 2 3

输出 #1

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]$$$,这是非递减的。