You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/256M

题目描述

在手工艺术课上，apiadu 正在制作一张贺卡。

他有一张长条形的彩纸，纸上已经画好了 $n$ 个紧挨着的矩形条，每个矩形条的宽度都是 $1$。从左到右数，第 $i$ 个矩形条的高度为 $a_i$。这些矩形条的底边都在同一条水平线上。

为了完成贺卡，apiadu 需要根据设计方案，从这张彩纸上剪下一个连续的片段。每次剪取时，他会选择一个区间 $[l, r]$，将第 $l$ 个到第 $r$ 个矩形条所组成的整体图形完整地裁剪下来。

为了评估裁剪的难度，apiadu 想知道他剪下的这个图形的总边界长度（即该几何图形的周长，包含底部切割线、顶部轮廓以及所有的侧边）。

由于 apiadu 可能会尝试多种不同的设计方案，他会向你询问 $q$ 次，请你针对每次询问的区间回答周长。

格式

输入格式

第一行包含两个正整数 $n, q$，分别表示矩形条的总数和询问的次数。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每个矩形条的高度。

接下来 $q$ 行，每行包含两个正整数 $l, r$（$1 \le l \le r \le n$），表示 apiadu 裁剪的区间。

输出格式

对于每次询问，输出一个整数，表示裁剪下来的图形周长。

样例

样例输入 #1

5 5
3 2 4 1 5
1 5
2 4
2 5
1 3
3 5

样例输出 #1

28
14
24
16
22

样例解释 #1

整个矩形条如下图所示。

对于样例 $2$，截取 $[2,4]$ 之间的矩形条，如下所示：

其周长为红色线段的长度，为 $2 + 1 + 2 + 1 + 3 + 1 + 1 + 3 = 14$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5$，$1 \le l \le r \le n$，$1 \le a_i \le 10^9$。