题目描述

小雨的日志：

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 \leq n,q \leq$	$0 \leq a_i,x,y \leq$
$1 \sim 3$	$5$	$10^5$
$4 \sim 6$	$50$
$7 \sim 10$	$25000$	$10^9$

样例输入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$