该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

给定一个长度为 $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$

输入格式

第一行一个正整数 $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]$ 。

输出格式

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

样例 1

输入

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

见下发文件 interval2.in/out.

说明/提示

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

数据范围

对全部测试数据，满足 $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$ 。