Truy vấn Tổng Thiếu

Cho $n$ đồng xu với giá trị dương. Bạn cần trả lời $q$ truy vấn: với mỗi truy vấn $[a,b]$, hỏi tổng nhỏ nhất không thể tạo thành bằng cách chọn một số đồng xu từ đoạn $[a,b]$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$: số đồng xu và số truy vấn.

Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\dots ,x_n$: giá trị các đồng xu.

• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$: phạm vi đồng xu của truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên: tổng nhỏ nhất không tạo được.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le x_i\le {10}^9$
• $1\le a\le b\le n$

Ví dụ