Cho mảng \(x_1,x_2,\ldots,x_n\) gồm \(n\) số nguyên. Bạn cần trả lời \(q\) truy vấn \((a,b)\). Trong một thao tác, được chọn một trong hai cách:

• sắp xếp \(a\) phần tử đầu tiên theo thứ tự không giảm; hoặc
• sắp xếp \(b\) phần tử cuối cùng theo thứ tự không giảm.

Với mỗi truy vấn, cần ít nhất bao nhiêu thao tác để sắp xếp toàn bộ mảng theo thứ tự không giảm? Mỗi truy vấn đều bắt đầu từ mảng ban đầu \(x_1,x_2,\ldots,x_n\).

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,q\), lần lượt là độ dài mảng và số truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(x_1,x_2,\ldots,x_n\).

\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a,b\).

Dữ liệu ra

Với mỗi truy vấn, in số thao tác ít nhất trên một dòng. Nếu không thể sắp xếp mảng, in -1.

Ràng buộc

• \(1\le n,q\le2\cdot10^5\).
• \(1\le x_i\le10^9\).
• Trong mọi truy vấn, \(1\le a,b\le n\).

Phân nhóm

1. \(6\) điểm: \(n,q\le10\) và \(a+b\le n\) trong mọi truy vấn.
2. \(5\) điểm: \(n,q\le10\).
3. \(7\) điểm: \(a+b\le n\) trong mọi truy vấn.
4. \(14\) điểm: \(1\le x_i\le2\).
5. \(23\) điểm: \(n,q\le5000\) và mảng là một hoán vị của \(1,2,\ldots,n\).
6. \(12\) điểm: \(n,q\le5000\).
7. \(33\) điểm: không có ràng buộc thêm.

6 3
3 1 4 1 5 9
4 1
3 3
2 5

1
-1
2

Ở truy vấn thứ nhất, chỉ cần sắp xếp \(4\) phần tử đầu. Truy vấn thứ hai không thể thực hiện được. Ở truy vấn thứ ba, trước hết sắp xếp \(2\) phần tử đầu, sau đó sắp xếp \(5\) phần tử cuối.

Nguồn

Baltic Olympiad in Informatics 2026 - đề và dữ liệu chính thức.