Hoán vị mảng con

Giới hạn thời gian mỗi test: 2 seconds

Giới hạn bộ nhớ mỗi test: 256 megabytes

Đầu vào: Đầu vào chuẩn

Đầu ra: Đầu ra chuẩn

Cho một mảng gồm n số tự nhiên phân biệt. Hãy sắp xếp mảng đã cho theo thứ tự không giảm bằng cách thực hiện lần lượt các thao tác sau một lần duy nhất:

1. Chia mảng đã cho thành chính xác k mảng con không rỗng sao cho mỗi phần tử ở mảng gốc chỉ thuộc đúng 1 mảng con;

2. Sắp xếp lại thứ tự của các mảng con tùy ý;

3. Hợp các mảng con lại theo thứ tự mới của nó.

Một mảng a là mảng con của mảng b nếu có thể tìm được a bằng cách xóa một số (có thể không xóa hoặc xóa tất cả) phần tử của mảng b từ vị trí đầu tiên về cuối hoặc từ vị trí cuối cùng lên đầu.

Bạn hãy viết một chương trình để cho biết có thể sắp xếp một mảng cho trước theo thứ tự không giảm bằng các thao tác nêu trên hay không.

Đầu vào

Dòng đầu tiên chứa một số nguyên t (1 ≤ t ≤ 10³) – số lượng các trường hợp kiểm thử. Mỗi trường hợp kiểm thử có cấu trúc như sau:

Dòng đầu tiên của mỗi trường hợp chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 10⁵).

Dòng thứ hai chứa n số nguyên a₁, a₂,…, ­a_n (0 ≤ |a_i| ≤ 10⁹, 1 ≤ i ≤ n). Đảm bảo rằng tất cả các số đều khác nhau.

Đảm bảo rằng tổng của n từ tất cả trường hợp kiểm thử không vượt quá 3 × 10⁵.

Đầu ra

Với mỗi trường hợp kiểm thử, chương trình in ra một xâu duy nhất.

Nếu có thể sắp xếp mảng đã cho theo thứ tự không giảm, in ra “YES” (không có dấu đóng mở ngoặc). Ngược lại, in ra “NO” (không có dấu đóng mở ngoặc).

Chú ý in ra đúng kí tự in hoa.

Trong trường hợp đầu tiên, a = [6, 3, 4, 2, 1], và k = 4, có thể thực hiện các thao tác sau:

1. Chia mảng a thành {[6], [3, 4], [2], [1]}.

2. Sắp xếp lại thành: {[1], [2], [3, 4], [6]}

3. Gộp lại thành [1, 2, 3, 4, 6], và thế là mảng a đã được sắp xếp theo thứ tự đúng.

Trong trường hợp thứ hai,  không có cách nào để sắp xếp mảng đã cho chỉ bằng cách tách nó ra thành 2 mảng con.