Truy vấn Tổng Thiếu

Cho $n$ đồng xu, đồng xu thứ $i$ có giá trị nguyên dương $x_i$. Bạn cần trả lời $q$ truy vấn.

Mỗi truy vấn cho một đoạn $[a,b]$. Hãy tìm số nguyên dương nhỏ nhất không thể viết thành tổng của một tập con các đồng xu có chỉ số nằm trong đoạn $[a,b]$ (mỗi đồng xu chỉ được dùng nhiều nhất một lần).

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.

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

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng riêng một số nguyên: tổng dươ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ụ