#T1001. 整理书架

整理书架

Description

小猿有一个装满书的书架,书籍按照编号顺序排列。由于小猿非常喜欢阅读,他经常会从书架上取下一本书来阅读,然后出于个人习惯,他只会将这本书放回书架的最开头,而不是原来的位置。这样的操作可能重复多次,导致书籍的顺序可能会被打乱。现在,小猿想要检查书架上的书是否能通过他的特殊操作变回非递减编号顺序(即每本书的编号都不小于它左边的书的编号)。

你的任务是帮助小猿判断,书架上的书是否可以仅通过将书架末端的书移动到书架开头的操作,重新变为非递减顺序。

Input

第一行包含一个整数 T,表示总共有 T 组测试数据。 对于每组测试数据: 第一行包含一个整数 n,表示书架上书的总数。 第二行包含 n 个整数,表示书架上每本书的编号。

1 ≤ T ≤ 100

1 ≤ n ≤ 100,000

书的编号满足 1 ≤ id ≤ 1,000,000,000

Output

对于每组测试数据,输出一行结果,如果书架上的书可以通过上述操作变为非递减顺序,则输出 YES,否则输出 NO。

Samples

2
5
3 4 5 1 2
4
4 3 2 1
YES
NO

Limitation

2
5
3 4 5 1 2
4
4 3 2 1

对于 第一组测试数据

初始状态:3 4 5 1 2

第一次操作:将 2 移动到开头,序列变为 2 3 4 5 1

第二次操作:将 1 移动到开头,序列变为 1 2 3 4 5

通过两次操作后,书籍编号顺序变为 1 2 3 4 5,这是一个非递减序列。因此,对于这组测试数据的答案是 YES。

对于 第二组测试数据

4
4 3 2 1

这组数据的初始状态是 4 3 2 1,这是一个递减序列。对于这样的序列,无论如何将末端的书移动到开头,都无法使序列变为非递减序列。因为在递减序列中,每次操作最多只能将当前最小的元素移动到前面,但这并不会改变其他元素之间递减的顺序关系。因此,无法通过指定的操作达到目标,对于这组测试数据的答案是 NO。