Problem Statement

You are given a permutation $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$.

For a sequence of integers $x=(x_1,x_2,\dots,x_k)$, define the score of $x$ as the number of indices $i$ satisfying $x_i < x_{i+1}$.

Process the following query $Q$ times.

• You are given positive integers $l$ and $r$ with $1 \le l \le r \le N$. For $X = (P_l,P_{l+1},\dots,P_r)$, solve the following problem.
• Let $M$ be the maximum score of a non-empty subsequence of $X$. Find the minimum length of a non-empty subsequence of $X$ whose score equals $M$.

What is a subsequence? A subsequence of a sequence $A$ is a sequence obtained by removing zero or more elements from $A$ and arranging the remaining elements in their original order.

Constraints

• $1 \le N,Q \le 2 \times 10^5$
• $P$ is a permutation of $(1,2,\dots,N)$.
• $1 \le l \le r \le N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
P_1\ P_2\ \dots\ P_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

l\ r

Output

Output $Q$ lines. The $i$-th line should contain the answer to $\mathrm{query}_i$.