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

题目描述

小柯的集训日记：

08:01 机房好吵！出去透透气吧！ 08:05 机房好吵！去买瓶水吧！ 08:10 机房好吵！去走廊晃一圈吧！ ......

于是第二天小柯就被教练约谈了。教练调取了门禁记录，统计了小柯昨天一整天离开机房和回到机房的所有时刻：

小柯一共回到了 $n$ 次机房，又 $n$ 次离开了机房

为了方便记录，教练按时间顺序整理出 $2 \times n$ 个时刻，依次为：小柯回到机房的时刻，小柯离开机房的时刻，小柯回到机房的时刻，小柯离开机房的时刻 $\dots$

教练表示：我倒要看看你一天里到底在机房坐了多长时间！

教练决定随机查看 $q$ 个时段的监控，每次查看时刻 $x$ 到 $y$ 之间，小柯有多长时间在机房里刷题

输入格式

输入第一行包含一个整数 $n$，含义如题

接下来一行包含 $2 \times n$ 个整数 $a_i$ 依次表示题目所述的时刻，保证 $a_i$ 互不相同且从小到大排序

第三行包含一个整数 $q$，含义如题

接下来 $q$ 行，每行包含两个整数 $x,y$ 表示查看的监控时段

输出格式

对于每次询问，输出一行一个整数，表示该时段内小柯在机房里的时长

输入输出样例 #1

输入 #1

2
2 6 10 17
2
0 3
8 20

输出 #1

1
7

输入输出样例 #2

输入 #2

3
1 4 6 9 12 20
4
2 3
5 13
4 6
0 100

输出 #2

1
4
0
14

说明/提示

数据范围

对于 $100\%$ 的数据满足 $1 \leq n,q \leq 25000$，$0 \leq a_i,x,y \leq 10^9$，保证 $a_i$ 互不相同且从小到大排序

样例解释1

小柯在机房的时间段为 $[2,6]$ 和 $[10,17]$。

$0$ 到 $3$ 之间只有 $[2,3]$ 这段时间在机房，所以时长为 $1$；$8$ 到 $20$ 之间只有 $[10,17]$ 这段时间在机房，所以时长为 $7$。

样例解释2

$2$ 到 $3$ 之间小柯都在机房，所以时长为 $1$

$5$ 到 $13$ 之间有 $[6,9],[12,13]$ 两段时间在机房，所以时长为 $4$

$4$ 到 $6$ 之间：$[1,4]$ 段只剩下 $4$ 这一个时刻，$[6,9]$ 段只剩下 $6$ 这一个时刻，单个时刻的长度为 $0$，所以时长为 $0$