给定长度为n的序列：a1,a2,…,an，记为a[1:n]。类似地，a[l:r]（1≤l≤r≤N）是指序列：a_l,a_l+1,…,a_r-
1,a_r。若1≤l≤s≤t≤r≤n，则称a[s:t]是a[l:r]的子序列。现在有q个询问，每个询问给定两个数l和r，1≤l≤r
≤n，求a[l:r]的不同子序列的最小值之和。例如，给定序列5,2,4,1,3，询问给定的两个数为1和3，那么a[1:3]有
6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，这6个子序列的最小值之和为5+2+4+2+2+2=17。

　　输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。接下来一行，包含n个整数，以空格隔开
,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。

　　对于每次询问，输出一行，代表询问的答案。

1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 100011; 
int n,m,belong[MAXN],ST[MAXN][18],l,r;
int last[MAXN],next[MAXN],stack[MAXN],top,block;
LL suml[MAXN],sumr[MAXN],A[MAXN],ans,a[MAXN];
struct ask{int l,r,id,lb;}q[MAXN];
inline bool cmp(ask q,ask qq){ if(q.lb==qq.lb) return q.r<qq.r; return q.lb<qq.lb; }
inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
    if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}

inline int query(int l,int r){
	int t=belong[r-l+1],cc=r-(1<<t)+1;
	if(a[ST[l][t]]<=a[ST[cc][t]]) return ST[l][t];
	return ST[cc][t];	
}

inline void updatel(int l,int r,int type){
	int from=query(l,r); LL suan=(r-from+1)*a[from]/*!!!*/;
	suan+=sumr[l]-sumr[from]; ans+=type*suan;
}

inline void updater(int l,int r,int type){
	int from=query(l,r); LL suan=(from-l+1)*a[from]/*!!!*/;
	suan+=suml[r]-suml[from]; ans+=type*suan;
}

inline void work(){ 
	n=getint(); m=getint(); for(int i=1;i<=n;i++) a[i]=getint(),ST[i][0]=i; block=sqrt(n);
	for(int i=1;i<=m;i++) q[i].l=getint(),q[i].r=getint(),q[i].id=i,q[i].lb=(q[i].l-1)/block+1;
	sort(q+1,q+m+1,cmp); int from;
	belong[1]=0; for(int i=2;i<=n;i++) belong[i]=belong[i>>1]+1; a[0]=(1<<30);
	for(int j=1;j<=17;j++) 
		for(int i=1;i<=n;i++) {
			from=i+(1<<(j-1));
			if(from<=n && a[ST[i][j-1]]<=a[ST[from][j-1]]) ST[i][j]=ST[i][j-1];
			else ST[i][j]=ST[from][j-1];
		}
	top=0; stack[0]=0;
	for(int i=1;i<=n;i++) {
		while(top>0 && a[i]<a[stack[top]]) next[stack[top]]=i,top--;
		last[i]=stack[top];	stack[++top]=i;
	}
	while(top>0) next[stack[top]]=n+1,top--;
	for(int i=1;i<=n;i++) suml[i]=suml[last[i]]+(LL)(i-last[i])*a[i];
	for(int i=n;i>=1;i--) sumr[i]=sumr[next[i]]+(LL)(next[i]-i)*a[i];
	ans=a[1]; l=r=1;
	for(int i=1;i<=m;i++) {
		while(r<q[i].r) r++,updater(l,r,1);
		while(l>q[i].l) l--,updatel(l,r,1);
		while(r>q[i].r) updater(l,r,-1),r--;
		while(l<q[i].l) updatel(l,r,-1),l++;
		A[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",A[i]);
}

int main()
{
    work();
    return 0;
}