Max's Anger Contest Series 2 P3 - Array Anger

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 3.0s
Java 5.0s
Python 5.0s
Memory limit: 1G

Problem type

To stave off his boredom from not having a Communication Credit next term, Wesley decided to yell at his array (the closest thing to an intern).

He will yell Q queries at his array, A, of N integers. The queries take the form OI L_i S_i, where his array will answer the first R that satisfies S_i \le \text{Sum}_{[L_{i}, R_{i}]} or N if no valid R_{i} exists (\text{Sum}_{[L, R]} denotes the sum of elements from the 1-indexed [L, R] in the array).

Since no one wants to be Wesley's intern, you are voluntold to be the array.

Can you answer these queries to prevent more yelling?


1 \le N \le 2 \times 10^{5}

1 \le Q \le 5 \times 10^{5}

1 \le A_{i} \le 5 \times 10^{3}

1 \le L_{i} \le N

1 \le S_{i} \le 10^{9}

Subtask 1 [30%]

1 \le N, Q \le 10^{3}

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line will contain two integers, N and Q, the number of array elements and the number of queries, respectively.

The next line will contain N integers, A_{i}, the elements of the array.

The next Q lines will contain one of the above queries, L_{i} and S_{i}, the start of the query and the minimum sum of the subarray.

Output Specification

Output Q lines with R_{i}, the answers to the queries.

Sample Input

6 6
1 5 3 2 1 7
OI 1 50
OI 1 19
OI 4 1
OI 1 12
OI 1 10
OI 2 8

Sample Output



There are no comments at the moment.