5463. 缺失硬币和查询（Missing Coin Sum Queries）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 你有 $n$ 枚硬币，硬币的面值都是正整数。硬币的编号从 $1$ 到 $n$。 你的任务是处理 $q$ 个查询，每个查询的形式为：'如果你只能使用编号在 $[a,b]$ 范围内的硬币，无法凑出的最小金额总和是多少？' ## 输入格式 第一行包含两个整数 $n$ 和 $q$，表示硬币的数量和查询数量。 第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$，表示每枚硬币的面值。 接下来 $q$ 行描述查询。每行两个整数 $a$ 和 $b$，表示你可以使用编号在 $a$ 到 $b$ 之间的硬币。 ## 输出格式 对于每个查询，输出无法凑出的最小金额。 ## 输入输出样例 ### 输入 #1 ``` 5 3 2 9 1 2 7 2 4 4 4 1 5 ``` ### 输出 #1 ``` 4 1 6 ``` ## 说明/提示 ### 数据规模与约定 - $1 \le n, q \le 2 \cdot 10^5$ - $1 \le x_i \le 10^9$ - $1 \le a \le b \le n$