Bạn có \(n\) đồng xu với các giá trị số nguyên dương. Các đồng xu được đánh số \(1,2,\ldots,n\).

Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: "nếu bạn có thể sử dụng các đồng xu \(a\ldots b\), số tiền nhỏ nhất mà bạn không thể tạo ra là gì?"

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q\): số lượng đông xu và truy vấn.
• Dòng thứ hai có n số nguyên \(x_1,x_2,\ldots,x_n\): giá trị của mỗi đồng xu.
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có hai giá trị \(a\) và \(b\): bạn có thể sử dụng các đồng xu \(a\ldots b\).

Output

• In câu trả lời cho từng truy vấn.

Constraints

• \(1 \leq n,q \leq 2 \cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)
• \(1 \leq a \leq b \leq n\)

Example

Sample input

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

Sample output

4
1
6

Note

Đầu tiên bạn có thể sử dụng các đồng xu \([9,1,2]\), sau đó là các đồng xu \([2]\) và cuối cùng là các đồng xu \([2,9,1,2,7]\).