题目背景

不顺我意者，当填在野之壑。

题目描述

在野之壑可以分为 $n$ 个等长的区域，第 $i$ 个区域的深度为 $a_i$。

孙綝会选择一个区间 $[l,r]$，往此区间中的每个区域都填入等量的不顺我意者。每个区域填入的数量为这些区域深度的最小值。

然而，有时候在野之壑中只有一些区域可用。因此你需要回答 $q$ 次询问，每次给定一个区间 $[L,R]$，表示在野之壑中只有 $[L,R]$ 内的区域可用，也就是选择的区间必须满足 $L\le l\le r\le R$。你要回答孙綝，所有的填入方案中，总共填入的不顺我意者数量之和。

输入格式

输入的第一行包含两个正整数 $n,q$。

输入的第二行包含 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。

接下来 $q$ 行，每行两个正整数 $L,R$。

输出格式

输出 $q$ 行，每行包含一个数，表示每次询问的答案。

样例 1 输入

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

样例 1 输出

27
48
5
14
19

子任务

对于所有测试数据，保证 $1\le n,q\le 2\times 10^5$，$1\le a_i\le 10^8$，$1\le L\le R\le n$。