全国人口普查开始了，小周周要去“幸福村”统计人口数量。和上一个题目（统计人口 I）相比，本题扩大了数据规模。
“幸福村”里住着 $n$ 户人家，呈线性排列，从左到右的编号为 $1$ 到 $n$。通过电脑平台，统计到了每户人家的人口数量 $a_i$。
当小周周去“幸福村”核查数据时，如果编号为 $x$ 到 $y$ 的都不在家（无法核查不在家的人口数量），求小周周能核查到多少人口数量？

第一行 $2$ 个整数 $n,\ m$。
第二行 $n$ 个数 $a_i$ 表示每户人家的人口数。 
接下来 $m$ 行，每行两个数 $x,\ y$，表示编号为 $x$ 到 $y$ 的不在家。

共 $m$ 行，每行一个数，表示当编号为 $x$ 到 $y$ 的不在家时，能核查到多少人口数量。

对于 $30\%$ 的数据，$1≤n≤100,\ 1≤m≤100$；
对于 $50\%$ 的数据，$1≤n≤1000,\ 1≤m≤10000$；
对于 $100\%$ 的数据，$1≤n≤50000,\ 1≤m≤50000,\ 1≤x≤y≤n$。
保证输出的所有答案不超 $2^{31}-1$ 范围。

6
10

有 $4$ 户，每户分别有 $3$ 人，$1$ 人，$5$ 人，$6$ 人。
当编号为 $1$∼$3$ 的不在家时，只能统计到第 $4$ 户的人口数量，有 $6$ 人；
当编号为 $3$∼$3$，也就是只有编号为 $3$ 的不在家时，能统计到第 $1,\ 2,\ 4$ 户的人口数量，共有 $10$ 人。