AT_abc305_d [ABC305D] Sleep Log

高桥君正在记录自己的睡眠情况。睡眠记录用一个奇数长度的数列 $A=(A_1(=0), A_2, \ldots, A_N)$ 表示，奇数下标表示起床时间，偶数下标表示入睡时间。更严格地说，在记录期间，高桥君的睡眠情况如下： - 对于所有满足 $1\leq i\leq\dfrac{N-1}{2}$ 的整数 $i$，高桥君在开始记录后的第 $A_{2i}$ 分钟正好入睡，在第 $A_{2i+1}$ 分钟正好醒来。 - 除此之外的时间段内，高桥君既没有入睡也没有醒来。 请回答接下来的 $Q$ 个询问。第 $i$ 个询问给出一组整数 $(l_i, r_i)$，满足 $0\leq l_i\leq r_i\leq A_N$。 - 从开始记录后的第 $l_i$ 分钟到第 $r_i$ 分钟这 $r_i-l_i$ 分钟内，高桥君睡着了多少分钟？

输入以如下格式从标准输入给出。 > $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $Q$ $l_1$ $r_1$ $l_2$ $r_2$ $\vdots$ $l_Q$ $r_Q$

请输出 $Q$ 行，每行输出第 $i$ 个询问的答案，结果为整数。

### 限制条件 - $3\leq N