\begin{problem}{Infection Investigation}{standard input}{standard output}{3 seconds}{1024 megabytes}

Isaac is a biologist who specializes in diagnosing viral diseases. The virus modifies the host genome (a~sequence of genes) by altering it to suit its own needs. Isaac is writing a paper investigating viral infection in genomes. He has some samples and asks you to help analyze them.

For simplicity, we will assume that the viral genome consists of genes $1, 2, \ldots, n$ in this order. The host genome is a permutation of genes $1, 2, \ldots n$: it consists of genes $a_1, a_2, \ldots, a_n$ in this order.

Consider a genomic segment $[l; r]$ consisting of genes $a_l, a_{l+1}, \ldots, a_r$. The infection level of this segment is measured as the length of the longest subsequence of genes shared with the viral genome. Formally, the infection level is the maximum $k$ such that there exist $l \le i_1 < i_2 < \dots < i_k \le r$ for which the inequalities $a_{i_1} < a_{i_2} < \dots < a_{i_{k}}$ hold.

To analyze the genome, Isaac needs to estimate the infection levels of $q$ genomic segments. To secure the funding, Isaac only needs approximate results: an error factor of up to $1.5$ is allowed.

%Formal statement is as follows:

% You are given an array $a_1, \ldots, a_n$ and $q$ queries of the form $(l, r)$. For each query, find the length of the longest increasing subsequence of $[a_l, \ldots, a_r]$. Since it might be a bit hard, you are allowed to be imprecise by a factor of 1.5.

\InputFile
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$, denoting the host genome length and the number of genomic segments Isaac is interested in ($1 \le n, q \le 2 \cdot 10^5$).

The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$, describing the host genome ($1 \le a_i \le n$).

Each of the following $q$ lines contains two integers $l$ and $r$, denoting the boundaries of a genomic segment for which the infection level should be estimated ($1 \le l \le r \le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$, and the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.

\OutputFile
For each test case, print $q$ positive integers, denoting the infection levels of the corresponding genomic segments.

For each genomic segment, let your answer be $x$ and let the true answer be $y$. Your answer will be considered correct if it differs from the true answer by a factor of at most $1.5$, that is, if $\max\left(\frac{x}{y}, \frac{y}{x}\right) \le 1.5$.

\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\end{problem}

