You are given an arr (len(arr) <= 1e5) (-1e9 <= arr[i] <= 1e9) and q (<= 1e5) queries, now each query is of the form, (l, r, x) (1 <= l <= r <= len(arr), x can be any 32 bit integer) for each query u need to output the sum(arr[i]) such that l <= i <= r and arr[i] >= x.

I am stuck with this problem can anyone solve this problem?

Can anyine solve this problem? Problem Link

Time limit: 1.00 s Memory limit: 512 MB

Statement

You have n coins with positive integer values. The coins are numbered 1, 2, ...., n. Your task is to process q queries of the form: "if you can use coins a ..... b, what is the smallest sum you cannot produce?"

Input

The first input line has two integers n and q: the number of coins and queries. The second line has n integers x_1, x_2, ......., x_n: the value of each coin. Finally, there are q lines that describe the queries. Each line has two values a and b: you can use coins a .... b.

Output

Print the answer for each query.

Constraints

• n , q <= 1e5
• x_i <= 1e9
• 1 <= a <= b <= n

Example Input:
5 3
2 9 1 2 7
2 4
4 4
1 5

Output:
4
1
6

Explanation: First you can use coins [9,1,2], then coins [2] and finally coins [2,9,1,2,7].