#include "meetings.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define ll long long
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define mod 1000000007
const ll INF=1e18;
const int MAXN=1e5;
ll tree[4*MAXN];
int n;
vector<ll> v;
void build(int node,int l,int r){
if(l==r){
tree[node]=v[l];
return;
}
int mid=(l+r)/2;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
tree[node]=max(tree[node<<1],tree[node<<1|1]);
}
ll query(int node,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tree[node];
int mid=(l+r)/2;
ll ans=0;
if(ql<=mid) ans=max(ans,query(node<<1,l,mid,ql,qr));
if(qr>mid) ans=max(ans,query(node<<1|1,mid+1,r,ql,qr));
return ans;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
n=H.size();
for(auto x:H){
v.push_back(x);
}
int q=L.size();
vector<ll> anss;
build(1,0,n-1);
for(int qu=0;qu<q;qu++){
int l=L[qu];
int r=R[qu];
ll BIGANS=INF;
for(int x=l;x<=r;x++){
ll ans=0;
for(int i=l;i<=r;i++){
// dbg(x,i,query(1,0,n-1,min(i,x),max(i,x)));
ans+=query(1,0,n-1,min(i,x),max(i,x));
}
// dbg(x,ans);
BIGANS=min(ans,BIGANS);
}
anss.push_back(BIGANS);
}
return anss;
}
#ifdef IOI
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "meetings.h"
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int N = read_int();
int Q = read_int();
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
H[i] = read_int();
}
std::vector<int> L(Q), R(Q);
for (int j = 0; j < Q; ++j) {
L[j] = read_int();
R[j] = read_int();
}
std::vector<long long> C = minimum_costs(H, L, R);
for (size_t j = 0; j < C.size(); ++j) {
printf("%lld\n", C[j]);
}
return 0;
}
#endif
