Truy vấn tổng xu bị thiếu (Missing Coin Sum Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ đồng xu, đồng xu $i$ có giá trị dương $x_i$. Mỗi truy vấn $a,b$ chỉ cho phép dùng các đồng xu có chỉ số trong $[a,b]$, mỗi đồng xu dùng nhiều nhất một lần. Hãy tìm số nguyên dương nhỏ nhất không thể biểu diễn thành tổng của một tập con các đồng xu được phép.

Dữ liệu vào

Dòng đầu chứa $n,q$. Dòng thứ hai chứa các giá trị $x_i$. Mỗi trong $q$ dòng sau chứa $a,b$.

Kết quả

Với mỗi truy vấn, in tổng dương nhỏ nhất không thể tạo được.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, số truy vấn $\le 3000$.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$
• $1\le x_i\le10^9$
• $1\le a\le b\le n$

Ví dụ

Input

5 3
2 9 1 2 7
2 4
4 4
1 5

Output

4
1
6

Giải thích

Với truy vấn [2,4], các xu là [9,1,2]. Ta tạo được $1,2,3$ nhưng không tạo được $4$, nên đáp án là $4$.