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

제한

노트