#P18575. A Near-Inversion Graph
A Near-Inversion Graph
A Near-Inversion Graph
给定一个由整数 构成的排列 ,需要回答 个询问。
每个询问给出两个整数 ,满足 。以闭区间 内的全部整数作为顶点建立一张无向图。对每对 ,当且仅当以下两个条件同时满足时,在顶点 之间加一条边:
- ;
- 不存在下标 ,使得 且 。
请计算这张图的连通分量数。
顶点是原排列的下标,比较的是这些下标处的排列值;第二个条件同时要求下标和值都严格位于相应两者之间。
输入格式
第一行包含一个整数 (),表示测试组数。
每组测试的第一行包含两个整数 (),表示排列长度和询问数。
第二行包含 个互不相同的整数 ()。
接下来 行,每行包含两个整数 (),描述一个询问。
所有测试的 之和不超过 。所有测试的 之和也不超过 ;这两个总限制分别成立。
输出格式
对每组测试,按询问顺序输出 个整数,表示对应图的连通分量数。可以每个答案输出一行。
样例
输入
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