#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
#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 split(int x)
{
vi sp;
int j = 0;
while (2 * (1 << j) <= x)
{
sp.push_back(1 << j);
x -= 1 << j;
sp.push_back(1 << j);
x -= 1 << j;
++j;
}
j = 0;
while (x > 0)
{
if (x & (1 << j))
sp.push_back(1 << j), x ^= 1 << j;
++j;
}
return sp;
}
ll numberOfSubsequences(ll n)
{
return n * (n + 1) / 2;
}
ll totalLengthOfSubsequences(ll n)
{
return n * (n + 1) * (n + 1) / 2 - (2 * n + 1) * (n + 1) * n / 6;
}
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;
A = vi(AA.begin() + l, AA.begin() + r);
}
ll n = sz(A);
vi heatMap(*max_element(all(A)) + 1, 0);
for (int i = 0; i < sz(A); ++i)
++heatMap[A[i]];
map<int, int> cnts;
for (int i = 0; i < sz(heatMap); ++i)
if (heatMap[i])
++cnts[heatMap[i]];
vpii S;
for (auto it = cnts.begin(); it != cnts.end(); ++it)
for (int x : split(it->second))
S.push_back({it->first, x});
ll pref = 0;
int num = sz(S);
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] = totalLengthOfSubsequences(n);
for (int j = 0; j < num; ++j)
{
int ii = j & 1;
int ni = ii ^ 1;
fill(all(dp[ni]), INF);
ll x = S[j].first; // how much
ll y = S[j].second; // how often
ll len = x * y;
ll subsure = 0;
// if both are in set
subsure += totalLengthOfSubsequences(len) - x * x * (totalLengthOfSubsequences(y) - y) - y * numberOfSubsequences(x);
// either with left or right endpoint in set
ll factor = len * (len + 1) / 2 - x * y * (y + 1) / 2;
subsure += factor * (n - len);
for (ll left = 0; left < min(pref + 1, (ll)sz(dp[ii])); ++left)
{
ll tmp = dp[ii][left];
if (tmp == INF)
continue;
tmp -= subsure;
// left
dp[ni][left + len] = min(dp[ni][left + len], tmp - (len - y) * left * (n - left - len));
// right
ll right = pref - left;
dp[ni][left] = min(dp[ni][left], tmp - (len - y) * right * (n - right - len));
}
pref += len;
}
ans = *min_element(all(dp[num & 1]));
cout << ans << "\n";
}
return 0;
}
