I. 感染调查（）

题目描述

Isaac 是一名研究病毒疾病诊断的生物学家。病毒会修改宿主的基因组，使其更适合自身需要。Isaac 正在撰写一篇关于基因组病毒感染的论文，希望你帮助分析一些样本。

为简化问题，假设病毒基因组依次由基因

$$1,2,\ldots,n$$

组成。

宿主基因组是 $1,2,\ldots,n$ 的一个排列，记为

$$a_1,a_2,\ldots,a_n.$$

考虑基因组中的一个区间 $[l,r]$，它包含基因

$$a_l,a_{l+1},\ldots,a_r.$$

该区间的感染程度定义为它与病毒基因组的最长公共子序列长度。等价地，感染程度是最大的整数 $k$，使得存在

$$l\le i_1<i_2<\cdots<i_k\le r$$

并满足

$$a_{i_1}<a_{i_2}<\cdots<a_{i_k}.$$

也就是说，感染程度就是子数组 $a_l,a_{l+1},\ldots,a_r$ 的最长严格递增子序列长度。

Isaac 需要估计 $q$ 个区间的感染程度。为了获得研究经费，他并不需要精确答案：允许答案与真实值之间相差至多 $1.5$ 倍。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

每组测试数据的第一行包含两个整数 $n,q$，分别表示宿主基因组长度和询问数量。

第二行包含 $n$ 个互不相同的整数

$$a_1,a_2,\ldots,a_n,$$

表示宿主基因组。

接下来 $q$ 行，每行包含两个整数 $l,r$，表示一个需要估计感染程度的区间。

输出格式

对于每组测试数据，输出 $q$ 个正整数，依次表示各个询问的答案。

对于任意一个询问，设你的答案为 $x$，真实的最长递增子序列长度为 $y$。当且仅当

$$\max\left(\frac{x}{y},\frac{y}{x}\right)\le 1.5$$

时，该询问的答案被认为正确。

整数之间可以用任意空白字符分隔。

数据范围

$$1\le t\le 10^4,$$ $$1\le n,q\le 2\times 10^5,$$ $$1\le a_i\le n,$$ $$1\le l\le r\le n.$$

所有测试数据中：

$$\sum n\le 2\times 10^5,\qquad \sum q\le 2\times 10^5.$$

样例

2
10 4
3 5 8 4 6 7 1 10 2 9
1 7
7 10
1 10
3 4
8 2
1 2 3 4 5 6 7 8
1 8
1 8

4
3
5
1
6
12

由于本题允许近似答案，样例输出只是众多合法输出中的一种。