Dandiao Stack Game

Problem Description

There are $n$ pairs $(a_i, b_i)$, numbered from $1$ to $n$.

There is an initially empty stack $S$. When inserting a pair $(a_i, b_i)$, first keep popping the top element until the stack is empty or the top element $(a_j, b_j)$ satisfies $a_i \neq a_j$ and $b_i < b_j$, then push $(a_i, b_i)$ onto the stack.

A pair is called "successful" if, after being pushed, it is the only element in the stack.

There are $q$ queries $[l_i, r_i]$. If the pairs with indices in $[l_i, r_i]$ are pushed onto the stack in increasing index order, how many of them are "successful"? The queries are independent of each other.

Input Format

The first line contains two positive integers $n, q$.

The second line contains $n$ positive integers, the values $a_i$.

The third line contains $n$ positive integers, the values $b_i$.

The following $q$ lines each contain two positive integers $l_i, r_i$, describing one query.

Output Format

$q$ lines, each containing a non-negative integer: the answer to the corresponding query.

Sample Input

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

Sample Output

3
2
2
3

Sample Explanation

Take the first query $[1, 4]$ as an example.

Initially the stack is $\{\}$.

After pushing pair $1$, the stack is $\{(3, 10)\}$; it has only one element, so this pair is "successful".

When pushing pair $2$ $(1, 10)$, the $b$ value of the top element $(3, 10)$ is not greater than that of pair $2$, so we pop. Now the stack is empty; pair $2$ is pushed, the stack becomes $\{(1, 10)\}$, so this pair is "successful".

When pushing pair $3$ $(3, 2)$, the top element has a different $a$ value and a larger $b$ value, so no popping is needed; pair $3$ is pushed directly, the stack becomes $\{(1, 10),(3, 2)\}$, which has multiple elements, so this pair is not "successful".

When pushing pair $4$ $(1, 9)$, the $b$ value of the top element $(3, 2)$ is smaller, so we pop. After popping, the top element $(1, 10)$ has the same $a$ value as $(1, 9)$, so we continue popping. Now the stack is empty; pair $4$ is pushed, the stack becomes $\{(1, 9)\}$, so this pair is "successful". In total $3$ pairs are "successful", hence the answer is $3$.

Constraints

$1 \leq n, q \leq 5 \times 10^5, 1 \leq a_i, b_i \leq n, 1 \leq l_i \leq r_i \leq n$.