[R44C]贺卡 - 代码源竞赛平台

时空限制

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 裁剪的区间。

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

整个矩形条如下图所示。

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

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

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

子任务编号	分数	$n, q\le$
$1$	$40$	$1000$
$2$	$60$	$2\times 10^5$

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