Background

After consideration by the administrators, we plan to store the unofficial testdata separately in the last subtask. The score of these test points is 0, but failing to pass any of them will be regarded as not passing this problem.

In this problem, there is an issue where the test point numbers in the judging records are in a wrong order, caused by a naming conflict of unofficial testdata. However, we guarantee that their relative order is not messed up.

Unofficial testdata provider: @Froggy.

Problem Description

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

There is an initially empty stack $S$. When inserting an element $(a_i, b_i)$ into it, repeatedly pop 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$, and then push $(a_i, b_i)$ onto the stack.

If, after an ordered pair is pushed, the stack contains only this one element, then this ordered pair is called “successful”.

There are $q$ queries $[l_i, r_i]$. For each query, if we push the ordered pairs with indices in $[l_i, r_i]$ into the stack one by one in increasing order of index, how many ordered pairs will be “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 representing $a_i$.

The third line contains $n$ positive integers representing $b_i$.

The next $q$ lines each contain two positive integers $l_i, r_i$, representing one query.

Output Format

Output $q$ lines. Each line contains one non-negative integer representing the answer to one query.

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

Hint

[Sample Explanation]

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

Initially, the stack is $\{\}$.

After pushing ordered pair $1$, the stack is $\{(3, 10)\}$. There is only one element in the stack, so this ordered pair is “successful”.

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

Push ordered pair $3$ $(3, 2)$. Now the top element has a different $a$ value from it, and has a larger $b$ value than it, so no popping is needed. Push ordered pair $3$ directly, and the stack becomes $\{(1, 10), (3, 2)\}$. The stack has multiple elements, so this ordered pair is not “successful”.

Push ordered pair $4$ $(1, 9)$. Now the top element $(3, 2)$ has a smaller $b$ value than it, so we pop it. After popping, the top element $(1, 10)$ has the same $a$ value as $(1, 9)$, so we continue popping. Now the stack is empty, so ordered pair $4$ is pushed, the stack becomes $\{(1, 9)\}$, and this ordered pair is “successful”. In total, there are $3$ “successful” ordered pairs, so the answer is $3$.

[Samples 2, 3, 4]

See the attachments $\texttt{stack/stack*.in}$ and $\texttt{stack/stack*.ans}$.

Link: https://pan.baidu.com/s/14XxLN63bxvpJAod81foGOg Extraction code: gugu.

[Constraints and Hints]

For all test points: $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$.

The specific limits for each test point are shown in the table below:

Translated by ChatGPT 5