3908: 张老师的摸鱼计划
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
张老师的工作日志：
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$，含义如题
接下来一行包含 $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$ | $10^5$ |
| $7 \sim 10$ | $25000$ | $10^9$ |
输出
对于每次询问，给出张老师在工位上的时长
样例输入 复制
2
1 3 5 7
1
2 5样例输出 复制
1提示
样例解释1
$2$ 到 $5$ 之间有 $[2,3]$ 这段时间张老师在工位上，所以时长为 $1$。
样例解释2
$0$ 到 $2$ 之间张老师在 $[1,2]$ 在工位上，所以时长为 $1$
$1$ 到 $3$ 之间张老师都在工位上，所以时长为 $2$
$2$ 到 $8$ 之间有 $[2,3],[5,7]$ 两段时间张老师在工位上，所以时长为 $3$
$2$ 到 $5$ 之间有 $[2,3]$ 这段时间张老师在工位上，所以时长为 $1$。
$0$ 到 $2$ 之间张老师在 $[1,2]$ 在工位上，所以时长为 $1$
$1$ 到 $3$ 之间张老师都在工位上，所以时长为 $2$
$2$ 到 $8$ 之间有 $[2,3],[5,7]$ 两段时间张老师在工位上，所以时长为 $3$