#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=5100;
const int LOGN=18;
ll lg[MAXN];
vector<ll> v;
int n;
ll st[MAXN][LOGN];
//sparse table
void build(){
for(int i=0;i<n;i++) st[i][0]=v[i];
for(int j=1;j<LOGN;j++){
for(int i=0;i+(1<<j)<=n;i++){
st[i][j]=max(
st[i][j-1],
st[i+(1<<(j-1))][j-1]
);
}
}
lg[1]=0;
for(int i=2;i<MAXN;i++){
lg[i]=lg[i/2]+1;
}
}
int query(int l,int r){
int k=r-l+1;
k=lg[k];
return max(
st[l][k],
st[r-(1<<k)+1][k]
);
}
//dp preprocess
int dp[MAXN][MAXN];//dp[x][i] is the prefix sum from dp[x][0] to dp[x][i] if we used x
void build2(){
for(int x=0;x<n;x++){
for(int i=0;i<n;i++){
dp[x][i]=query(min(i,x),max(i,x));
}
}
}
ll prefsum(int x,int l,int r){
ll ans=0;
for(int i=l;i<=r;i++){
ans+=dp[x][i];
}
return ans;
return dp[x][r]-((l==0)?0LL:dp[x][l-1]);
}
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();
build2();
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++){
BIGANS=min(BIGANS,prefsum(x,l,r));
}
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
