/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 3e5 + 10, maxq = 5e4 + 10;
const int block_size = sqrt(maxn);
struct query
{
int l, r, idx;
} task[maxq];
bool cmp_mo(query t1, query t2)
{
if (t1.l / block_size == t2.l / block_size)
return t1.r < t2.r;
return t1.l < t2.l;
}
int q, a[maxn], freq[maxn], comp[maxn];
ll n;
///unordered_map < int, int > act;
int act[maxn];
bitset < maxn > bt;
void update(int val, int c)
{
///cout << "update " << val << " " << c << endl;
if (freq[val] != 0)
{
act[freq[val]] --;
if (act[freq[val]] == 0)
bt[freq[val]] = 0;
}
///comp[freq[val]] --;
freq[val] += c;
///comp[freq[val]] ++;
if (freq[val] != 0)
{
act[freq[val]] ++;
bt[freq[val]] = 1;
}
}
int lf = 1, rf = 0;
ll ans[maxn];
void move_borders(int left, int right)
{
while(rf < right)
{
rf ++;
update(a[rf], 1);
}
while(lf > left)
{
lf --;
update(a[lf], 1);
}
while(rf > right)
{
update(a[rf], -1);
rf --;
}
while(lf < left)
{
update(a[lf], -1);
lf ++;
}
}
ll arr[maxn], bef[maxn], aft[maxn], prec[maxn];
ll calc_function(ll len)
{
vector < pair < ll, ll > > values;
int bit = bt._Find_first();
while(bit < maxn)
{
values.push_back({bit, act[bit]});
bit = bt._Find_next(bit);
}
/**
for (pair < int, int > cur : act)
{
values.push_back(cur);
}
sort(values.begin(), values.end());*/
ll sz = values.size(), cp = 0;
deque < pair < ll, ll > > dq;
ll left_add = 0, right_add = 0;
values.back().second --;
cp ++;
dq.push_back({values.back().first, 1});
for (int i = sz - 1; i >= 0; i --)
{
ll p1 = (values[i].second + 1) / 2;
ll p2 = (values[i].second) / 2;
if (right_add > left_add)
swap(p1, p2);
if(p1 != 0)
dq.push_back({values[i].first, p1});
if (p2 != 0)
dq.push_front({values[i].first, p2});
cp += values[i].second;
left_add += p2;
right_add += p1;
}
ll tot = 0, pref = 0;
for (int i = 0; i < dq.size(); i ++)
{
ll l = dq[i].second;
tot = tot + l * pref * pref;
tot = tot + l * (l + 1) * pref * dq[i].first;
tot = tot + prec[l] * dq[i].first * dq[i].first;
pref = pref + dq[i].first * l;
///cout << pref << " " << tot << " " << dq[i].first << " " << dq[i].second << endl;
}
tot = tot - pref * pref;
ll suff = 0;
for (int i = dq.size() - 1; i >= 0; i --)
{
ll l = dq[i].second;
tot = tot + l * suff * suff;
tot = tot + l * (l + 1) * suff * dq[i].first;
tot = tot + prec[l] * dq[i].first * dq[i].first;
suff = suff + dq[i].first * l;
}
tot = tot - suff * suff;
tot = (cp * len * (len + 1) - len * (cp - 1) - tot) / 2;
return tot;
}
void compress_data()
{
int cur = 0;
map < int, int > mp;
for (int i = 1; i <= n; i ++)
{
if (mp[a[i]] == 0)
mp[a[i]] = ++ cur;
a[i] = mp[a[i]];
}
}
void solve()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++)
cin >> a[i];
for (int i = 1; i <= n; i ++)
{
prec[i] = prec[i - 1] + (ll)(i) * (ll)(i);
}
compress_data();
for (int i = 1; i <= q; i ++)
{
cin >> task[i].l >> task[i].r;
task[i].idx = i;
}
sort(task + 1, task + q + 1, cmp_mo);
for (int i = 1; i <= q; i ++)
{
move_borders(task[i].l, task[i].r);
ans[task[i].idx] = calc_function(task[i].r - task[i].l + 1);
}
for (int i = 1; i <= q; i ++)
cout << ans[i] << endl;
}
int main()
{
speed();
///freopen("test.txt", "r", stdin);
solve();
return 0;
}
