暂无测试数据。

题目描述

有 $n$ 个二元组 $(a_i,b_i)$，编号为 $1$ 到 $n$。

有一个初始为空的栈 $S$，向其中加入元素 $(a_i,b_i)$ 时，先不断弹出栈顶元素直至栈空或栈顶元素 $(a_j,b_j)$ 满足 $a_i\neq a_j$ 且 $a_i<b_j$，然后再将其加入栈中。

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

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

询问之间相互独立。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个正整数表示 $a_i$。

第三行 $n$ 个正整数表示 $b_i$。

接下来 $q$ 行，每行两个正整数 $l_i,r_i$，表示一组询问。

输出格式

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

数据范围

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