Background

At 3:35 a.m., Atom dragged his roommate into a Codeforces competition. After a fierce battle, he successfully reached the rank of Candidate Master. Just as he was overjoyed, reality presented him with a harsh challenge…

Problem Statement

It’s now 5:35 a.m., and Atom has become a Candidate Master, but he realizes that he’s about to attend Professor E’s class, course S. To avoid failing the course while maximizing his sleep, Atom decides to face the challenge as a Candidate Master.

Course S consists of $n$ lessons, each with an importance value $a_i$. Meanwhile, there are $m$ parallel universes, and in each one, Professor E has a specific tolerance value $k_j$ and knows the first class $l_j$ that Atom will sleep through after the Codeforces competition. Professor E will fail Atom if he skips any lesson with an importance value greater than or equal to $k_j$.

Atom will start sleeping from the $l_j$-th lesson and will sleep through at least that lesson. He wants to know, in each parallel universe, the maximum number of consecutive lessons he can sleep through without failing. If failing is unavoidable, output all in acm; otherwise, output the maximum number of lessons he can sleep through.

Input

The first line contains two positive integers $n$ and $m$, representing the number of lessons and the number of parallel universes $(1 \leq n, m \leq 5 \times 10^5)$.

The second line contains $n$ positive integers $a_i$, representing the importance value of each lesson $(1 \leq a_i \leq 10^9)$.

The next $m$ lines each contain two positive integers $k_j$ and $l_j$, representing Professor E’s tolerance value and the lesson index from which Atom starts sleeping $(1 \leq k_j \leq 10^9, 1 \leq l_j \leq n)$.

Output

Output $m$ lines, each containing an integer or a string. For each parallel universe:

• If Atom cannot avoid failing, output all in acm.
• Otherwise, output the maximum number of consecutive lessons he can sleep through.

Example

Input

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

Output

1
3
all in acm
2

Constraints

• For $30\%$ of the test cases, $1 \leq n, m \leq 5 \times 10^3$.
• For $100\%$ of the test cases, $1 \leq n, m \leq 5 \times 10^5$.
• $1 \leq a_i \leq 10^9$
• $1 \leq k_j \leq 10^9$
• $1 \leq l_j \leq n$