At the University of Squirreloo, first-year squirrels in the math faculty have to take MATH 137: calculus, everyone's favourite branch of math! In this course they learn about convergent sequences, where values in a sequence get arbitrarily close to a limit. However, said sequences are infinite, and infinity is a concept too difficult to tackle immediately for our young squirrels, so they'll first discuss sequences of finite length - namely, an array of length ~N~. We'll say an array ~A~ converges to a limit ~L~ with an accuracy of ~\epsilon~ if there exists a suffix ~B~ of ~A~ such that all elements in ~B~ differ from ~L~ by at most ~\epsilon~. Given an array ~A~ of length ~N~, the squirrels are given ~Q~ assignment questions of the form ~(L,\epsilon)~, and are tasked to determine whether or not ~A~ converges to ~L~ with an accuracy of ~\epsilon~, and if so, to find the length of the longest suffix of ~A~ that fulfills the definition above.

Constraints

For this problem, you will be required to pass all the samples in order to receive any points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

~1 \le N,Q \le 200\,000~
~0 \le |a_i| \le 10^9~ for all ~1 \le i \le N~
~0 \le |L|, \epsilon \le 10^9~

Subtask 1 [18%]

~1 \le N, Q \le 5\,000~

Subtask 2 [82%]

No additional constraints.

Input Specification

On the first line will be two integers ~N~ and ~Q~, the length of the array and the number of assignment questions respectively.

The second line will contain ~N~ integers ~a_1, \dots, a_n~, the array ~A~.

The following ~Q~ lines will each contain two integers ~L_i~ and ~\epsilon_i~, the limit and accuracy to test for on the ~i^{th}~ assignment question.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output ~Q~ lines. The ~i^{th}~ line should contain the length of the longest suffix of ~A~ such that all elements in the suffix differ from ~L_i~ by at most ~\epsilon_i~. If such a suffix does not exist, output ~0~.

Sample Input 1

8 5
1 5 4 6 -2 3 4 0
0 4
2 2
1 5
-1 0
5 5

Sample Output 1

4
3
8
0
3

Sample Input 2

5 5
1 2 3 4 5
5 1
4 1
2 2
2 3
1 5

Sample Output 2

2
3
0
5
5