说明

小 L 和小 C 在一起生活的的每一天都可以用一个二元组 $(a_i,c_i)$ 表示。$c_i$ 要么是 $0$ ，要么是 $1$，代表这天小 L 和小 C 有没有吵架。而 $a_i$ 则是一个整数，代表这一天小 C 的心情值。

小 L 和小 C 正在同时进行 $m$ 场家庭战争。第 $k$ 场战争从第 $l_k$ 天开始。

由于他们的战争非常激烈，你不知道他们在第几天会结束这场战争。但如果这场战争于第 $r$ 天结束，且从第 $l_k$ 天到第 $r$ 天吵架的天数恰好为 $d_k$，那么这场战争就会给小 C 带来一定的怨气值。怨气值为第 $l_k$ 天到第 $r$ 天小 C 心情值的逆序对个数。否则，小 C 的怨气值就为 $0$。

现在，小 L 把这 $n$ 天的 $(a_i,c_i)$ 和 $m$ 场战争的 $l_k$ 和 $d_k$ 告诉了你。对于每场战争，小 L 希望知道对于所有可能的结束时间，小 C 的怨气值之和，以便他挽回和小 L 的感情。他会非常感激你的帮助，并给你 $7420738134810 \bmod 12673$ 元作为感谢。

形式化题意

你有 $n$ 个二元组 $(a_{i},c_{i})$，其中满足 $c_{i} \in \{0,1\}$。

现在有 $m$ 个询问，每次询问给出两个整数 $l_{k},d_{k}$，求：

$$\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}]$$

其中中括号内的式子若为真，则其值为 $1$，否则为 $0$。

输入格式

第一行一个整数 $n$，表示序列长度。

接下来 $n$ 行，每行两个整数 $a_{i},c_{i}$，表示小 L 和小 C 在一起生活的第 $n$ 天的描述二元组。

然后一行一个整数 $m$，表示战争的场数。

接下来 $m$ 行，每行两个整数 $l_{k},d_{k}$，代表一次战争。

输出格式

输出 $m$ 行，表示每次战争中，对于的所有可能的结束时间，小 C 的怨气值之和。

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

1
5

提示

样例解释 $1$

对于询问 $1$，只有区间 $[3,4]$ 符合条件，所以答案为 $1$。

对于询问 $2$，只有区间 $[1,4]$ 符合条件，所以答案为 $5$。

数据范围

测试点编号	$n,m\le$	特殊性质
$1$	$100$	无
$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\sim 17$		D
$18\sim20$	$5\times10^4$	无
$21\sim25$	$10^5$

特殊性质 A：保证 $c_i=0$。

特殊性质 B：保证 $d_{k}=1$。

特殊性质 C：保证 $c_i=1$。

特殊性质 D：保证询问中 $\forall k<m,l_{k} \le l_{k+1},d_{k} \le d_{k+1}$。

对于 $100\%$ 的数据，$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$。

保证此题的时空限制是标程的 2 倍及以上。