#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9,SqrtN = 359,M = 1e5 + 9,V = 1e5 + 9,SqrtV = 359;
int n,m;
int a[N];
int tmp[N],top;
struct Block{
	struct block{
		int l,r;
	} b[SqrtN];
	int block_len,block_cnt;
	int belong[N];
	void build_block(int n){
		block_len = sqrt(n);block_cnt = (n + block_len - 1) / block_len;
		for(int i = 1;i <= block_cnt;i++){
			b[i].l = b[i - 1].r + 1;
			b[i].r = b[i].l + block_len - 1;
		}
		b[block_cnt].r = n;
		for(int i = 1;i <= block_cnt;i++)
			for(int j = b[i].l;j <= b[i].r;j++)
				belong[j] = i;
	}
} block1,block2;
struct Query{
	int l,r;
	int id;
} q[M];
bool cmp(Query q1,Query q2){
	return (block1.belong[q1.l] ^ block1.belong[q2.l]) ? block1.belong[q1.l] < block1.belong[q2.l] : q1.r < q2.r;
}
struct Query_node{
	int l,r;//l,r这段区间对前缀产生贡献
	int ans;
};
struct Query2{
	vector<Query_node> vec;
	int pos;
	int get(){
		return vec[pos++].ans;
	}
} q2[N];
void add_query(int l,int r,int pre){
	q2[pre].vec.push_back((Query_node){l,r,0});
}
int bucket[V];
int tag[SqrtV];
void update(int l,int r){
	int pos_l = block2.belong[l],pos_r = block2.belong[r];
	if(pos_l == pos_r){
		for(int i = l;i <= r;i++)
			bucket[i]++;
		return;
	}
	for(int i = l;i <= block2.b[pos_l].r;i++)
		bucket[i]++;
	for(int i = block2.b[pos_r].l;i <= r;i++)
		bucket[i]++;
	for(int i = pos_l + 1;i <= pos_r - 1;i++)
		tag[i]++;
}
int query(int i){
	return bucket[i] + tag[block2.belong[i]];
}
int s[N];
void solve(){
	//扫描线 
	for(int i = 1;i <= n;i++){
		s[i] = query(a[i]);
		update(1,a[i] - 1);
		for(int j = 0;j < (int)q2[i].vec.size();j++)
			for(int i2 = q2[i].vec[j].l;i2 <= q2[i].vec[j].r;i2++)
				q2[i].vec[j].ans += query(a[i2]);
	}
}
int ans[M];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	block1.build_block(n);
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		tmp[++top] = a[i];
	}
	sort(tmp + 1,tmp + top + 1);
	top = unique(tmp + 1,tmp + top + 1) - tmp - 1;
	for(int i = 1;i <= n;i++)
		a[i] = lower_bound(tmp + 1,tmp + top + 1,a[i]) - tmp;
	block2.build_block(top);

	for(int i = 1;i <= m;i++){
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1,q + m + 1,cmp);
	int lres = 1,rres = 0;
	for(int i = 1;i <= m;i++){
		int L = q[i].l,R = q[i].r;
		if(rres < R)
			add_query(rres + 1,R,lres - 1);
		if(rres > R)
			add_query(R + 1,rres,lres - 1);
		rres = R;
		if(lres < L)
			add_query(lres,L - 1,rres);
		if(lres > L)
			add_query(L,lres - 1,rres);
		lres = L;
	}
	solve();
	for(int i = 1;i <= n;i++)
		s[i] += s[i - 1];
	int tmp = 0;
	lres = 1;rres = 0;
	for(int i = 1;i <= m;i++){
		int L = q[i].l,R = q[i].r;
		if(rres < R){
			tmp += s[R] - s[rres];
			tmp -= q2[lres - 1].get();
		}
		if(rres > R){
			tmp -= s[rres] - s[R];
			tmp += q2[lres - 1].get();
		}
		rres = R;
		if(lres < L){
			tmp -= q2[rres].get();
			tmp += s[L - 1] - s[lres - 1];
		}
		if(lres > L){
			tmp += q2[rres].get();
			tmp -= s[lres - 1] - s[L - 1];
		}
		lres = L;
		if(L == R)
			tmp = 0;
		ans[q[i].id] = tmp;
	}
	for(int i = 1;i <= m;i++)
		cout << ans[i] << '\n';
	return 0;
}