题目描述

有 $n$ 个整数排成一个圆圈，位置编号为 $1$ 到 $n$，每个整数的范围在 $-100$ 到 $100$ 之间。现在有 $m$个询问，每次询问给出两个整数 $x, y$（$0 < x, y \le n$），请你计算从位置 $x$ 开始，沿顺时针方向到位置 $y$ 所经过的所有整数的和。具体规则如下：

• 如果 $x \le y$，表示从 $x$ 到 $y$ 的连续段（包含两端）；
• 如果 $x > y$，表示从 $x$ 开始沿顺时针到 $n$，再从 $1$ 到 $y$（即跨越圆圈首尾的区间）。

请你求出这 $m$ 个计算结果中的最大值。

输入格式

第一行包含两个整数 $n, m$，分别表示整数的个数和询问的次数。

第二行包含 $n$ 个整数，表示圆圈上从位置 $1$ 到位置 $n$ 的数值，整数之间用空格隔开。

接下来 $m$ 行，每行包含两个整数 $x, y$，表示一次询问。

输出格式

一行，一个整数，表示所有询问结果中的最大值。

样例

5 3
3 -2 4 6 9
1 5
1 4
3 1

22

样例解释

• 第一次询问：$x=1 \le y=5$，和为 $3 + (-2) + 4 + 6 + 9 = 20$。
• 第二次询问：$x=1 \le y=4$，和为 $3 + (-2) + 4 + 6 = 11$。
• 第三次询问：$x=3 > y=1$，顺时针方向为位置 $3 \to 4 \to 5 \to 1$，和为 $4 + 6 + 9 + 3 = 22$。
  所有结果中最大值为 $22$。

数据范围

• $2 \le n \le 100000$
• $1 \le m \le 100000$
• 数组元素的范围：$-100 \le a_i \le 100$
• $1 \le x, y \le n$