题目描述

强哥最近在幼儿园学习，学习可真是忙得不可开交！但强哥有个小毛病，一旦学习太累了，总喜欢找各种理由溜达一圈：

这是强哥每天的日常：

8:00:01 学习

8:00:02 学习

8:00:03 学习

8:00:04 学习

8:00:05 学习

8:00:06 学习

8:00:07 学习

8:00:08 学习

8:00:09 学习

8:00:10 学习

$\vdots$

8:01 “哎呀，学习好辛苦！去洗把脸吧！”

9:04:01 学习

9:04:02 学习

$\vdots$

9:05 “哎呀，学习好辛苦！去吹吹风吧！”

10:09:01 学习

10:09:02 学习

$\vdots$

10:10 “哎呀，学习好辛苦！去喝杯水吧！”

11:23 “哎呀，学习好辛苦！去买包糖吧！”

12:30 “哎呀，学习好辛苦！去聊会天吧！”

13:30:01 学习

13:30:02 "哎呀，……"

$\vdots$

忙碌了一天的小强哥心想：“今天也是充实的一天呢” 。

结果第二天，幼儿园的园长就找强哥“谈心”了。

园长可是个细心的人，他统计了强哥一天里所有回到座位和离开座位的时间点。按照顺序，园长给出了 $2n$ 个时间点，分别是：强哥回到座位的时刻、强哥离开座位的时刻、强哥又回到座位的时刻……一直这样循环。

园长盯着这些时间点，严肃地说：“我倒要看看你昨天到底学习了多长时间！”

为了搞清楚，园长决定随机查看 $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$