1005. E. TREE

题目描述

给定一个长度为 (n) 的排列 (a_1,a_2,\ldots,a_n)。

对于一个非空序列 (b_1,b_2,\ldots,b_k)，它的小根笛卡尔树是一棵满足以下条件的二叉树：

1. 结点为序列中的 (k) 个位置；
2. 中序遍历依次得到位置 (1,2,\ldots,k)；
3. 每个结点对应的值都小于其儿子对应的值。

因为序列中的数互不相同，所以它的小根笛卡尔树唯一。

树根的深度定义为 (1)，其余结点的深度等于父亲深度加 (1)。树的高度是所有结点深度的最大值。

有 (q) 次询问。每次给定一个区间 ([l,r])，独立地取出序列

建立它的小根笛卡尔树，并求出这棵树的高度。

数据范围

• (1\le T\le10)；
• (1\le n,q\le2\times10^5)；
• (a_1,a_2,\ldots,a_n) 是 (1,2,\ldots,n) 的一个排列；
• (1\le l\le r\le n)；
• 所有测试数据的 (n) 之和不超过 (4\times10^5)；
• 所有测试数据的 (q) 之和不超过 (4\times10^5)。

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 (n,q)；
• 第二行包含 (n) 个整数 (a_1,a_2,\ldots,a_n)；
• 接下来 (q) 行，每行包含两个整数 (l,r)，表示一次询问。

输出格式

对于每次询问，输出一行一个整数，表示对应区间的小根笛卡尔树高度。

样例输入

3
1 2
1
1 1
1 1
5 6
3 1 5 2 4
1 5
1 3
3 5
2 4
3 3
4 5
7 6
3 2 4 1 6 5 7
1 7
1 3
5 7
2 6
3 5
4 4

样例输出

1
1
3
2
2
3
1
2
3
2
2
3
2
1

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1005