Mê Cung Số Nguyên Tố

Buổi 62 — Sqrt Decomposition & Mo
Points
50
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho dãy N số nguyên dương a_1, a_2, ..., a_N (mỗi a_i ≤ 1000). Có Q truy vấn, mỗi truy vấn cho l, r. Với mỗi truy vấn, tìm MEX (Minimum EXcludant) của tập các giá trị trong đoạn [l, r]. MEX là số nguyên không âm nhỏ nhất không xuất hiện trong tập.

Lưu ý: MEX tính trên tập giá trị, bắt đầu từ 0. Ví dụ MEX({1, 2, 3}) = 0, MEX({0, 1, 3}) = 2.

Để thuận tiện, ta định nghĩa MEX bắt đầu từ 1: MEX là số nguyên dương nhỏ nhất không xuất hiện trong đoạn.

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q (1 ≤ N, Q ≤ 100000). Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N (1 ≤ a_i ≤ 1000). Q dòng tiếp theo, mỗi dòng chứa hai số nguyên l, r (1 ≤ l ≤ r ≤ N).

Dữ liệu ra

Với mỗi truy vấn, in ra MEX (số nguyên dương nhỏ nhất không xuất hiện) trong đoạn [l, r].

Ví dụ
Input Output
5 3\n1 2 3 1 2\n1 5\n1 3\n2 4 4\n4\n4
Giới hạn
  • 1 ≤ N, Q ≤ 100000
  • 1 ≤ a_i ≤ 1000
  • 1 ≤ l ≤ r ≤ N
Draft saved