#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;
if (x == 1)
sp.push_back(1);
else
{
sp.push_back(x / 2);
sp.push_back(x / 2);
if (x & 1)
sp.push_back(1);
}
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 left = 0, right = 0;
int num = sz(S);
ans = totalLengthOfSubsequences(n);
for (int j = 0; j < num; ++j)
{
ll x = S[j].first; // how much
ll y = S[j].second; // how often
ll len = x * y;
// if both are in set
ans -= totalLengthOfSubsequences(len) - x * x * (totalLengthOfSubsequences(y) - y) - y * numberOfSubsequences(x);
// if one is inside the other isn't
ans -= (n - len) * (len * (len + 1) / 2 - x * y * (y + 1) / 2);
// if both are outside
ans -= (len - y) * left * (n - left - len);
left += len;
swap(left, right);
}
cout << ans << "\n";
}
return 0;
}
