Bessie vừa được tặng một bộ dụng cụ vẽ và muốn sơn hàng rào dài ở một đầu đồng cỏ. Hàng rào gồm \(N\) đoạn liên tiếp, mỗi đoạn dài 1 mét (\(1\le N\le2\cdot10^5\)). Bessie có \(N\) màu khác nhau, được đánh số \(1\) đến \(N\) theo độ đậm tăng dần: \(1\) rất nhạt và \(N\) rất đậm. Vì vậy, màu mong muốn của từng đoạn hàng rào được mô tả bằng một mảng \(N\) số nguyên.

Ban đầu, mọi đoạn hàng rào đều chưa được sơn. Trong một nét cọ, Bessie có thể tô một đoạn liên tiếp bất kỳ bằng một màu duy nhất, miễn là cô không bao giờ sơn màu nhạt hơn lên trên màu đậm hơn; cô chỉ có thể phủ màu đậm lên màu nhạt.

Ví dụ, một đoạn chưa tô có độ dài bốn có thể được sơn như sau:

0000 -> 1110 -> 1122 -> 1332

Không may, Bessie không có thời gian chờ sơn khô nên có thể phải để một số đoạn hàng rào chưa sơn. Cô đang xét \(Q\) đoạn ứng viên (\(1\le Q\le2\cdot10^5\)), mỗi đoạn được mô tả bởi hai số nguyên \((a,b)\) với \(1\le a\le b\le N\), là hai đầu mút của đoạn \(a\ldots b\) cần sơn.

Với mỗi đoạn ứng viên, hãy tính số nét cọ ít nhất để sơn mọi đoạn hàng rào bên trong đúng màu mong muốn, đồng thời giữ mọi đoạn bên ngoài chưa sơn. Bessie không thực sự sơn trong quá trình này, nên đáp án của các ứng viên độc lập với nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\).

Dòng tiếp theo chứa một mảng \(N\) số nguyên, biểu thị màu mong muốn của từng đoạn hàng rào.

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\), cách nhau bởi dấu cách, mô tả một đoạn ứng viên cần sơn.

Dữ liệu ra

Với mỗi ứng viên trong \(Q\) ứng viên, in đáp án trên một dòng mới.

Phân nhóm

• Các test 1-2 thỏa mãn \(N,Q\le100\).
• Các test 3-5 thỏa mãn \(N,Q\le5000\).
• Trong các test 6-10, mảng đầu vào không chứa số nguyên nào lớn hơn \(10\).
• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

8 4
1 2 2 1 1 2 3 2
4 6
3 6
1 6
5 8

2
3
3
3

Nguồn

USACO 2021 February Contest, Platinum - No Time to Dry: https://usaco.org/index.php?page=viewproblem2&cpid=1116

Tác giả: Andi Qu, Brian Dean và Benjamin Qi.