题目描述

徐老师的工作日志：

13:01 工作实在是太辛苦了！去洗把脸吧！ 13:05 工作实在是太辛苦了！去吹个风吧！ 13:10 工作实在是太辛苦了！去喝杯水吧！ 13:23 工作实在是太辛苦了！去买包糖吧！ 13:30 工作实在是太辛苦了！去聊会天吧！ ......

于是第二天徐老师就被老板约谈了，老板统计了徐老师昨天一天离开工位和回到工位的所有时刻：

徐老师一共回到了 $n$ 次工位，又 $n$ 次离开了工位

为了方便记录，老板会给出 $2 * n$ 个时刻，依次为：徐老师回到工位的时刻，徐老师离开工位的时刻，徐老师回到工位的时刻，徐老师离开工位的时刻 $\dots$

老板表示：我倒要看看你一天里到底工作了多长时间！

老板决定随机查看 $q$ 个时段的视频，每次查看时刻 $x$ 到 $y$ 之间，徐老师有多长时间在工位上工作

输入格式

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

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

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

接下来 $q$ 行，每行表示两个整数 $x,y$ 表示查看的视频时刻

输出格式

对于每次询问，给出徐老师在工位上的时长

数据范围

样例输入1

2
1 3 5 7
1
2 5

样例输出1

1

样例解释1

$2$ 到 $5$ 之间有 $[2,3]$ 这段时间徐老师在工位上，所以时长为 $1$。

样例输入2

2
1 3 5 7
3
0 2
1 3
2 8

样例输出2

1
2
3

样例解释2

$0$ 到 $2$ 之间徐老师在 $[1,2]$ 在工位上，所以时长为 $1$ $1$ 到 $3$ 之间徐老师都在工位上，所以时长为 $2$ $2$ 到 $8$ 之间有 $[2,3],[5,7]$ 两段时间徐老师在工位上，所以时长为 $3$