Description

Each day that Xiao L and Xiao C spend together can be represented by a tuple $(a_i, c_i)$. Here, $c_i$ is either $0$ or $1$, indicating whether Xiao L and Xiao C had a quarrel on that day. $a_i$ is an integer representing Xiao C's mood value on that day.

Xiao L and Xiao C are simultaneously engaged in $m$ family wars. The $k$-th war starts on the $l_k$-th day.

Since their wars are very intense, you do not know on which day they will end. However, if the war ends on the $r$-th day, and the number of quarrel days from the $l_k$-th day to the $r$-th day is exactly $d_k$, then this war will bring Xiao C a certain amount of resentment value. The resentment value is the number of inversion pairs in Xiao C's mood values from the $l_k$-th day to the $r$-th day. Otherwise, Xiao C's resentment value is $0$.

Now, Xiao L has provided you with the $(a_i, c_i)$ for all $n$ days and the $l_k$ and $d_k$ for the $m$ wars. For each war, Xiao L wants to know the sum of Xiao C's resentment values over all possible ending times, so he can try to mend their relationship. He will be very grateful for your help and reward you with $7420738134810 \bmod 12673$ yuan as thanks.

Formal Description

You have $n$ tuples $(a_{i}, c_{i})$, where $c_{i} \in \{0,1\}$.

There are $m$ queries. Each query provides two integers $l_{k}$ and $d_{k}$. Compute:

$$\sum_{r=l_{k}}^{n} \left[\left(\sum_{i=l_{k}}^{r} c_{i}\right)=d_{k}\right] \sum_{i=l_{k}}^{r} \sum_{j=i+1}^{r} [a_{j}<a_{i}]$$

Here, the expression in square brackets evaluates to $1$ if true, and $0$ otherwise.

Input Format

The first line contains an integer $n$, the length of the sequence.

The next $n$ lines each contain two integers $a_{i}$ and $c_{i}$, describing the tuple for the $i$-th day.

The next line contains an integer $m$, the number of wars.

The next $m$ lines each contain two integers $l_{k}$ and $d_{k}$, representing a war.

Output Format

Output $m$ lines, each indicating the sum of resentment values for all possible ending times in the corresponding war.

4
4 0
5 1
3 0
2 1
2
3 1
1 2

1
5

Hint

Sample Explanation 1

For the first query, only the interval $[3,4]$ meets the condition, so the answer is $1$.

For the second query, only the interval $[1,4]$ meets the condition, so the answer is $5$.

Data Range

Test Case ID	$n,m \leq$	Special Properties
$1$	$100$	None
$2,3$	$10^3$
$4,5$	$10^5$	A
$6\sim8$		B
$9,10$		CD
$11,12$	$5\times10^4$	C
$13,14$	$10^5$
$15\sim17$		D
$18\sim20$	$5\times10^4$	None
$21\sim25$	$10^5$

Special Property A: All $c_i=0$.

Special Property B: All $d_{k}=1$.

Special Property C: All $c_i=1$.

Special Property D: For all queries, $\forall k<m$, $l_{k} \le l_{k+1}$ and $d_{k} \le d_{k+1}$.

For $100\%$ of the data: $1\le n,m\le10^5$, $1\le l_k\le n$, $1\le a_i\le10^9$, $c_{i} \in \{0,1\}$, $0\le d_k\le 10^9$.

The time and memory limits for this problem are at least twice those of the standard solution.

Translation by DeepSeek R1