#P18575. A Near-Inversion Graph

A Near-Inversion Graph

A Near-Inversion Graph

给定一个由整数 1,2,…,n1,2,\ldots,n 构成的排列 p1,p2,…,pnp_1,p_2,\ldots,p_n,需要回答 qq 个询问。

每个询问给出两个整数 ℓ,r\ell,r,满足 1≤ℓ≤r≤n1\le\ell\le r\le n。以闭区间 [ℓ,r][\ell,r] 内的全部整数作为顶点建立一张无向图。对每对 ℓ≤i<j≤r\ell\le i<j\le r,当且仅当以下两个条件同时满足时,在顶点 i,ji,j 之间加一条边:

  1. pi>pjp_i>p_j;
  2. 不存在下标 kk,使得 i<k<ji<k<j 且 pi>pk>pjp_i>p_k>p_j。

请计算这张图的连通分量数。

顶点是原排列的下标,比较的是这些下标处的排列值;第二个条件同时要求下标和值都严格位于相应两者之间。

输入格式

第一行包含一个整数 tt(1≤t≤1041\le t\le10^4),表示测试组数。

每组测试的第一行包含两个整数 n,qn,q(1≤n,q≤5⋅1051\le n,q\le5\cdot10^5),表示排列长度和询问数。

第二行包含 nn 个互不相同的整数 p1,p2,…,pnp_1,p_2,\ldots,p_n(1≤pi≤n1\le p_i\le n)。

接下来 qq 行,每行包含两个整数 ℓ,r\ell,r(1≤ℓ≤r≤n1\le\ell\le r\le n),描述一个询问。

所有测试的 nn 之和不超过 5⋅1055\cdot10^5。所有测试的 qq 之和也不超过 5⋅1055\cdot10^5;这两个总限制分别成立。

输出格式

对每组测试,按询问顺序输出 qq 个整数,表示对应图的连通分量数。可以每个答案输出一行。

样例

输入

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

输出

1
3
3
4
4
2
4