#pragma GCC optimize ("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int BLOCK_SIZE = 540;
struct query {
int st, dr, id;
query() {}
query(int _st, int _dr, int _id) : st(_st), dr(_dr), id(_id) {}
bool operator<(const query& other) const {
return make_pair(st / BLOCK_SIZE, ((st / BLOCK_SIZE) & 1) ? -dr : dr) < make_pair(other.st / BLOCK_SIZE, ((other.st / BLOCK_SIZE) & 1) ? -other.dr : other.dr);
}
};
int v[300005];
int f[300005];
int cnt[545];
map <int, int> mp;
vector <int> v2;
vector < pair <int, int> > v3;
vector <query> qr;
ll r2[50005];
int main()
{
int n, i, x, q;
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (i = 1; i <= n; i++) {
cin >> v[i];
}
for (i = 1; i <= q; i++) {
int st, dr;
cin >> st >> dr;
qr.push_back(query(st, dr, i));
}
sort(qr.begin(), qr.end());
int l = 1, r = 0;
for (auto x : qr) {
while (r < x.dr) {
r++;
f[v[r]]++;
mp[f[v[r]]]++;
if (f[v[r]] != 1) {
mp[f[v[r]] - 1]--;
if (mp[f[v[r]] - 1] == 0) mp.erase(f[v[r]] - 1);
}
}
while (l > x.st) {
l--;
f[v[l]]++;
mp[f[v[l]]]++;
if (f[v[l]] != 1) {
mp[f[v[l]] - 1]--;
if (mp[f[v[l]] - 1] == 0) mp.erase(f[v[l]] - 1);
}
}
while (r > x.dr) {
f[v[r]]--;
mp[f[v[r]]]++;
mp[f[v[r]] + 1]--;
if (mp[f[v[r]] + 1] == 0) mp.erase(f[v[r]] + 1);
r--;
}
while (l < x.st) {
f[v[l]]--;
mp[f[v[l]]]++;
mp[f[v[l]] + 1]--;
if (mp[f[v[l]] + 1] == 0) mp.erase(f[v[l]] + 1);
l++;
}
int n2 = x.dr - x.st + 1;
int st = 0, dr = 0;
ll s2 = 0;
v3.clear();
for (auto x : mp) v3.push_back(x);
sort(v3.begin(), v3.end());
for (auto x : v3) {
s2 += 1LL * x.second * (1LL * x.first * (n2 - x.first) + 1LL * x.first * (x.first + 1) / 2);
if (st > dr) swap(st, dr);
int c1 = (x.second >> 1) + (x.second & 1);
int c2 = (x.second >> 1);
s2 += 1LL * c1 * st * (n2 - st - x.first) + 1LL * c1 * (c1 - 1) / 2 * x.first * (n2 - x.first) - 1LL * c1 * (c1 - 1) * (2 * c1 - 1) * x.first * x.first / 6 - 2LL * st * c1 * (c1 - 1) / 2 * x.first;
st += c1 * x.first;
s2 += 1LL * c2 * dr * (n2 - dr - x.first) + 1LL * c2 * (c2 - 1) / 2 * x.first * (n2 - x.first) - 1LL * c2 * (c2 - 1) * (2 * c2 - 1) * x.first * x.first / 6 - 2LL * dr * c2 * (c2 - 1) / 2 * x.first;
dr += c2 * x.first;
}
r2[x.id] = s2;
}
for (i = 1; i <= q; i++) cout << r2[i] << "\n";
}
