Range-Constrained Equal Pair Counting

You are given two integers \(n\) and \(m\), and two sequences:

• An array \(a_1, a_2, \dots, a_n\).
• A permutation \(y_1, y_2, \dots, y_n\) of \(\{1,2,\dots,n\}\).

You need to answer \(m\) queries. For each query, you are given two integers \(l\) and \(r\). For every pair \(1 \le i

[ \min_{k=i}^{j} y_k \ge l \quad \text{and} \quad \max_{k=i}^{j} y_k \le r, ]

then the pair is counted. Formally, the answer for a query is defined as:

[ \sum_{i=1}^{n}\sum_{j=i+1}^{n} [a_i = a_j] \cdot \prod_{k=i}^{j} [l \le y_k \le r], ]

where ([\mathrm{cond}]) equals (1) if the condition is true and (0) otherwise.

Note: The product \(\prod_{k=i}^{j} [l \le y_k \le r]\) is \(1\) if every element in the subarray \(y_i, y_{i+1}, \dots, y_j\) lies in the interval \([l, r]\), and \(0\) otherwise.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\).

The third line contains \(n\) distinct integers \(y_1, y_2, \dots, y_n\), which form a permutation of \(\{1, 2, \dots, n\}\).

Each of the following \(m\) lines contains two integers \(l\) and \(r\) representing a query.

outputFormat

For each query, output a single line containing the answer.

sample

3 2
1 2 1
1 2 3
1 3
2 3

1
0