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.