A1769.排序

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

AA 有一个由 nn 个整数组成的数组 aa,他希望 ACAC 狗按照非递减的顺序重新对数组进行排序。由于这对 ACAC 狗来说太容易了,小 AA 只允许 ACAC 狗使用下面的操作:

  • 选择数组的下标 iijj,如果 ijx|i-j| \geq x,则可以交换元素 aia_iaja_j

请你帮 ACAC 狗判断,是否可以使用上面的操作让数组变为一个有序序列(非递减)。

输入格式

每个测试包含多个测试用例。

第一行包含测试用例的数量 TT (1T1001 \le T \le 100)。

每个测试用例的第一行包含两个整数 nnxx (1xn1051 \le x \le n \le 10^5)。

每个测试用例的第二行包含 nn 整数 a1a_1 ~ ana_n(1ai1091 \le a_i \le 10^9)。

输出格式

如果 ACAC 狗可以使用上面的操作让数组变为一个有序序列(非递减),则输出 YES。否则,输出 NO

输入输出样例

  • 输入#1

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

    输出#1

    NO
    YES
    YES
    YES

说明/提示

第一个测试用例中,任何一个元素都不能交换,无法排序。

第二个测试用例中,数组已经有序。

第三个测试用例中,可以进行如下操作:

  • [5,1,2,3,4]swap(a1,a3)[5,1,2,3,4] ,swap(a_1,a_3)
  • [2,1,5,3,4]swap(a2,a5)[2,1,5,3,4] ,swap(a_2,a_5)
  • [2,4,5,3,1]swap(a2,a4)[2,4,5,3,1] ,swap(a_2,a_4)
  • [2,3,5,4,1]swap(a1,a5)[2,3,5,4,1] ,swap(a_1,a_5)
  • [1,3,5,4,2]swap(a2,a5)[1,3,5,4,2] ,swap(a_2,a_5)
  • [1,2,5,4,3]swap(a3,a5)[1,2,5,4,3] ,swap(a_3,a_5)
  • [1,2,3,4,5][1,2,3,4,5]
首页