#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 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
for (int i = 0; i < y; ++i)
{
// if both are in set
ans += -totalLengthOfSubsequences(x) + numberOfSubsequences(x);
// if on is inside the other isn't
ans -= (x - 1) * x / 2 * (n - x);
// if both are outside
ans -= (x - 1) * left * (n - left - x);
left += x;
swap(left, right);
}
}
cout << ans << "\n";
}
return 0;
}
