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