题目背景

翻译自 CSES-2184 题。

题目描述

你有 $n$ 个硬币，每个硬币有一个正整数的面值。硬币的编号为 $1, 2, \dots, n$。

你的任务是处理 $q$ 个查询，每个查询的形式是：“如果你可以使用硬币 $a$ 到 $b$，那么无法构成的最小总和是多少？”

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示硬币的数量和查询的数量。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$，表示每个硬币的面值。

接下来有 $q$ 行，每行包含两个整数 $a$ 和 $b$，表示你可以使用从硬币 $a$ 到硬币 $b$（包含这两个硬币）的所有硬币。

输出格式

对于每个查询，输出你无法用所选硬币构成的最小总和。

样例

5 3
2 9 1 2 7
2 4
4 4
1 5

4
1
6

样例1解释

• 第一个查询，你可以使用硬币 $[9, 1, 2]$，最小无法构成的总和是 $4$。
• 第二个查询，你可以使用硬币 $[2]$，最小无法构成的总和是 $1$。
• 第三个查询，你可以使用硬币 $[2, 9, 1, 2, 7]$，最小无法构成的总和是 $6$。

说明/提示

$1 \leq n, q \leq 2 \times 10^5$；

$1 \leq x_i \leq 10^9$；

$1 \leq a \leq b \leq n$。