You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个长度为 $N$ 的数列 $A_1,A_2,\dots,A_N$ 和一个长度为 $N-1$ 的数列 $B_2,B_3,\dots,B_N$。​

有 $Q$ 个询问，每次询问是一个区间 $[L_i,R_i]$ 。请你求出有多少二元组 $(l,r)$ 满足：

• $L_i \leq l < r \leq R_i$

• $\forall i\in\{l+1,l+2,\dots,r-1\}, A_l>A_i$ （如果 $l+1=r$ 则忽略这一条件，认为符合）

• $\forall i\in\{l,l+1,\dots,r-1\}, B_r>A_i$

输入格式

从 interval.in 文件读入数据。

​第一行一个正整数 $N$。

​第二行 $N$ 个正整数 $A_1, A_2, \dots, A_N$。

​第三行 $N-1$ 个正整数 $B_2, B_3, \dots, B_N$。

​第四行一个正整数 $Q$ ，代表有 $Q$ 个询问。

​接下来 $Q$ 行，每行两个整数 $L_i, R_i (1 \le L_i < R_i \le N)$ ，由一个空格隔开，表示第 $i$ 次的询问区间为 $[L_i,R_i]$ 。

输出格式

输出到 interval.out 文件。

​输出 $Q$ 行，每行一个整数，代表对应询问的答案。

样例

8
5 3 4 4 2 3 2 1
5 4 7 5 3 5 7
3
2 5
4 7
1 8

3
4
11

对于第三个询问，合法的区间有：$(2, 3),(1, 4),(3, 4),(4, 5),(5, 6),(4, 7),(6, 7),(1, 8),(4, 8),(6, 8),(7, 8)$ 。

样例 2

点击链接 ex_interval2.in 和 ex_interval2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对全部测试数据，满足 $2 \le N,Q \le 3 \times 10^5,1 \le L < R \le N,1 \leq A_i \leq 10^9, 1 \leq B_i \leq 10^9$ 。