有 n 个二元组 (ai,bi)，编号为 1 到 n。
有一个初始为空的栈 S，向其中加入元素 (ai,bi) 时，先不断弹出栈顶元素直至栈空或栈顶元素(aj,bj) 满足 ai != aj 且 bi<bj，然后再将其加入栈中。
如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。
有 q 个询问 [li,ri]，表示若将编号在 [li,ri] 中的二元组按编号从小到大依次入栈，会有多少个二元组是“成功的”。
询问之间相互独立。

第一行两个正整数 n,q。
第二行 n 个正整数表示 ai。
第三行 n 个正整数表示 bi。
接下来 q 行，每行两个正整数 li,ri，表示一组询问。

q 行，每行一个自然数表示一组询问的答案。

样例一解释：


以第一次询问 [1, 4] 为例。
一开始栈为 {}。
加入 1 号二元组后栈为 {(3,10)}，栈中只有一个元素，该二元组是“成功的”。
加入 2 号二元组 (1, 10) 时，栈顶的 (3, 10) 的 b 值不大于 2 号二元组的，因此弹栈。此时栈空，2 号二元组入栈，栈为 {(1,10)}，该二元组是“成功的”。
加入 3 号二元组 (3, 2)，此时栈顶元素与之 a 值不同，b 值比它更大，因而不需要弹栈，直接将 3 号二元组入栈，栈为 {(1,10),(3,2)}，栈中有多个元素，该二元组不是“成功的”。
加入 4 号二元组 (1, 9)，此时栈顶元素 (3, 2) 的 b 值比它小，弹栈。弹栈后栈顶元素 (1, 10) 与 (1, 9) 的 a 值相同，继续弹栈。此时栈空，4 号二元组入栈，栈为 {(1,9)}，该二元组是“成功的”。共有 3 个二元组是“成功的”，因而答案为 3。




样例二：
stack





【数据范围与提示】
对于所有测试点：1≤n,q≤5×10⁵，1≤ai,bi≤n，1≤li≤ri≤n。
每个测试点的具体限制见下表：

测试点编号	特殊性质
1∼3	n,q≤1000
4∼6	n≤5000
7∼10	n,q≤105
11∼12	bi=n−i+1
13∼15	ai=i
16∼20	无

NOIONLINE 2022 提高组 第一题