Ferume đã hỏi tôi liệu tôi có thể giải bài này nhanh hơn $O(n\sqrt{n} \log n)$ hay không. Và hóa ra là tôi làm được! Cảm ơn anh ấy vì đã tạo ra bài toán này và không để nó tồn tại với một lời giải nhàm chán.

Cho $S$ là một đa tập hợp chứa các số nguyên không âm. Bạn có thể thực hiện thao tác sau trên $S$ một số lần tùy ý (có thể bằng không): chọn $x$ sao cho có ít nhất hai lần xuất hiện của $x$ trong $S$, xóa một lần xuất hiện của $x$ nhưng thay vào đó chèn một lần xuất hiện của $(x - 1)$ hoặc $(x + 1)$ (bạn chỉ có thể chèn $(x - 1)$ nếu nó không âm). Gọi $F(S)$ là giá trị mex lớn nhất mà bạn có thể đạt được với các thao tác này. Ở đây, $\text{mex}(S)$ là số nguyên không âm nhỏ nhất không có mặt trong $S$.

Bạn được cho một mảng $a$ có độ dài $n$ và $q$ truy vấn $[l; r]$. Với mỗi truy vấn, hãy tìm $F(\{a_l, a_{l+1}, \dots, a_r\})$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n, q$ ($1 \le n, q \le 5 \cdot 10^5$) — kích thước của mảng và số lượng truy vấn.

Dòng thứ hai chứa mảng các số nguyên $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 5 \cdot 10^5$).

$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — truy vấn thứ $i$.

Dữ liệu ra

In ra câu trả lời cho các truy vấn theo thứ tự xuất hiện trong dữ liệu vào, mỗi câu trả lời trên một dòng.

Ví dụ

Dữ liệu vào 1

3 3
0 0 2
1 3
2 3
3 3

Dữ liệu ra 1

3
1
0

Dữ liệu vào 2

3 2
1 2 2
1 2
1 3

Dữ liệu ra 2

0
3