#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const ll INF = 1e18;
int N, Q;
vi A, AA;
ll ans;
vi P;
vi answerPermutation;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> Q;
AA.resize(N);
for (int i = 0; i < N; ++i)
cin >> AA[i];
while (Q--)
{
int l, r;
cin >> l >> r;
--l;
ll n = r - l;
A = vi(AA.begin() + l, AA.begin() + r);
vi heatMap(*max_element(all(A)) + 1, 0);
for (int i = 0; i < sz(A); ++i)
++heatMap[A[i]];
vi cnts;
for (int i = 0; i < sz(heatMap); ++i)
if (heatMap[i])
cnts.push_back(heatMap[i]);
sort(all(cnts));
vi pref(sz(cnts));
partial_sum(all(cnts), pref.begin());
ll num = sz(cnts);
vi dp[2];
for (int foo = 0; foo < 2; ++foo)
dp[foo].reserve(N + 1), dp[foo].resize(N + 1);
fill(all(dp[0]), INF);
dp[0][0] = n * (n + 1) * (n + 1) / 2 - (2 * n + 1) * (n + 1) * n / 6;
for (int j = 0; j < num; ++j)
{
int ii = j & 1;
int ni = ii ^ 1;
fill(all(dp[ni]), INF);
ll x = cnts[j];
ll subsure = 0;
// either with left or right endpoint in set
subsure += (n - x) * x * (x - 1) / 2;
// if both are in set
subsure += x * x * (x - 1) / 2 - (2 * x - 1) * x * (x - 1) / 6;
for (ll left = 0; left < sz(dp[ii]); ++left)
{
ll tmp = dp[ii][left];
if (tmp == INF)
continue;
tmp -= subsure;
// left
dp[ni][left + x] = min(dp[ni][left + x], tmp - (x - 1) * left * (n - left - x));
// right
ll right = pref[j] - x - left;
dp[ni][left] = min(dp[ni][left], tmp - (x - 1) * right * (n - right - x));
}
}
ans = *min_element(all(dp[num & 1]));
cout << ans << "\n";
}
return 0;
}
