- 描述
-
给定一个长度为 n 的整数数组 A=[A1,A2,...,An]。
你可以进行至多一次如下操作：
- 选择整数 i (1 ≤ i < n)，并将 A1,A2,...Ai 移动至最右侧，即数组变成 A=[Ai+1,...,An,A1,A2,...,Ai]。
请问，能否进行至多一次操作（也可以不操作），使得新数组是单调数组。
单调数组的定义为：A1 ≤ A2 ≤ ... ≤ An 成立或 A1 ≥ A2 ≥ ... ≥ An 成立。
- 输入
- 第一行包含一个整数 t (1≤t≤10000) 表示测试数据个数。
接下来 t 组测试数据，每组两行：
第一行包含一个整数 n (1≤n≤2*105) 表示元素个数。
第二行包含 n 个整数 Ai (-109≤Ai≤109) 表示每个元素。
保证所有测试数据的 n 的总和不超过 4*105。 - 输出
- 共 t 行，每行一个单词 Yes 或 No。如果可以通过至多一次操作得到单调数组，则输出 Yes，否则输出 No。
- 样例输入
-
11 5 3 4 5 1 2 4 1 3 5 7 3 30 20 10 1 100 2 5 20 8 3 10 10 10 20 -1000 -1000 3 4 9 8 8 9 4 9 3 5 1 5 3 4 5 2 1 10 1 2 3 4 5 5 4 3 2 1 2 5 5
- 样例输出
-
Yes Yes Yes Yes Yes Yes Yes No No No Yes
- 提示
- 【数据范围和约定】
对于30%的数据，n≤1000, 并且所有数据 n 的总和不超过 5000。
对于另外30%的数据，n≤2*105 并且所有 Ai 均两两不同;
对于全部100%的数据，1≤n≤2*105, -109≤Ai≤109, 1≤t≤10000, 并且所有数据 n 的总和不超过 4*105。
