#6166. [NOI Online 2022 提高组] 丹钓战 暂未评定

有 个二元组 ，编号为 到 。

有一个初始为空的栈 ，向其中加入元素 时，先不断弹出栈顶元素直至栈空或栈顶元素 满足 且 ，然后再将其加入栈中。

如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。

有 个询问 ，表示若将编号在 中的二元组按编号从小到大依次入栈，会有多少个二元组是“成功的”。

询问之间相互独立。

从文件 stack.in 中读入数据。

第一行两个正整数 。

第二行 个正整数表示 。

第三行 个正整数表示 。

接下来 行，每行两个正整数 ，表示一组询问。

输出到文件 stack.out 中。

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

样例输入

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

样例输出

3
2
2
3

样例解释

以第一次询问 为例。

一开始栈为 。

加入 号二元组后栈为 ，栈中只有一个元素，该二元组是“成功的”。

加入 号二元组 时，栈顶的 的 值不大于 号二元组的，因此弹栈。此时栈空， 号二元组入栈，栈为 ，该二元组是“成功的”。

加入 号二元组 ，此时栈顶元素与之 值不同， 值比它更大，因而不需要弹栈，直接将 号二元组入栈，栈为 ，栈中有多个元素，该二元组不是“成功的”。

加入 号二元组 ，此时栈顶元素 的 值比它小，弹栈。弹栈后栈顶元素 与 的 值相同，继续弹栈。此时栈空， 号二元组入栈，栈为 ，该二元组是“成功的”。共有 个二元组是“成功的”，因而答案为 。

样例2,3,4

stack.zip

对于所有测试点：，，。

每个测试点的具体限制见下表：