#ifdef LOCAL
#else
#endif // LOCAL
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#endif // LOCAL
const int N = 5600;
int n, q;
int mx[N][N];
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r)
{
n = h.size();
q = l.size();
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
if (j - 1 >= i) mx[i][j] = mx[i][j - 1];
mx[i][j] = max(mx[i][j], h[j]);
}
}
vector<long long> ans(q);
for (int i = 0; i < q; i++)
{
long long res = 1e18;
for (int a = l[i]; a <= r[i]; a++)
{
long long si = 0;
for (int b = l[i]; b <= r[i]; b++)
{
si += max(mx[a][b], mx[b][a]);
}
res = min(res, si);
}
ans[i] = res;
}
return ans;
}
#ifdef LOCAL
signed main()
{
int n0, q0;
cin >> n0 >> q0;
vector<int> h(n0), l(q0), r(q0);
for (int i = 0; i < n0; i++)
{
cin >> h[i];
}
vector<long long> ans = minimum_costs(h, l, r);
for (int i = 0; i < ans.size(); i++) cout << ans[i] << "\n";
}
#endif // LOCAL
