P14608 [NWRRC 2025] Infection Investigation

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.

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$.

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$.