虽然我已经写出了正解，但我还是想把大模拟做到三十分

#include<bits/stdc++.h>
using namespace std;
#define N 300003
int n,q,a[N],p[N],t[N],res,ans[N],cnt,x[N],y[N];
int e[N],w[N],ne[N],h[N],idx;
bool st[N],dist[N];
vector<vector<pair<int,int> > >m;
void add(int a, int b, int c) {
	ne[++idx] = h[a];
	e[idx] = b;
	w[idx] = c;
	h[a] = idx;
}
int W(int b,int e) {
//	for(int i=b;i<=e;i++)t[i]=0;
	for(int i=b; i<=e; i++)p[i]=a[i];
	if(b==e)return 0;
	int mid=(b+e)/2;
	W(b,mid);
	W(mid+1,e);
	int l=b,r=mid+1,k=b;
	while(l<=mid&&r<=e) {
		if(p[l]<=p[r])t[k]=p[l],k++,l++;
		else t[k]=p[r],k++,r++,res+=mid-l+1;
	}
	while(l<=mid)t[k]=p[l],k++,l++;
	while(r<=e)t[k]=p[r],k++,r++;
	for(int i=b; i<=e; i++)p[i]=t[i];
	return res;
}
void dij(int s) {
	for (int i = 1; i <= n; i++) {
		st[i] = 0;
		dist[i] = 1e9;
	}
	priority_queue<pair<int,int> > qu;
	dist[s] = 0;
	qu.push(make_pair(0,s));
	while (qu.size()) {
		int u = qu.top().second;
		qu.pop();
		if (st[u] == 1)continue;
		st[u] = 1;
		for (int i = h[u]; i; i = ne[i]) {
			int v = e[i];
			if (dist[u] + w[i] < dist[v]) {
				dist[v] = dist[u] + w[i];
				qu.push(make_pair(-dist[v], v));
			}
		}
	}
}
int main() {
	cin>>n>>q;
	for(int i=1; i<=n; i++)cin>>a[i];
	for(int i=1; i<=n; i++)
		for(int j=i+1;j<=n;res=0,j++)
			add(i,j,W(i,j));
	for(int i=1;i<=q;i++){
		cin>>x[i]>>y[i];
		m.resize(x[i]+1);
		m[x[i]].push_back(make_pair(y[i],i));
	}
	for(int i=0;i<m.size();i++){
		if(!m[i].size())continue;
		dij(i);
		for(int j=0;j<m[i].size();j++)
			ans[m[i][j].second]=dist[m[i][j].first];
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
	return 0;
}