#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
using namespace std;
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 rng(228);
//#ifdef LOCAL
// #define __int128 ll
//#endif // LOCAL
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
bool umn(T& a, T b) {
return a > b ? a = b, 1 : 0;
}
template <typename T>
bool umx(T& a, T b) {
return a < b ? a = b, 1 : 0;
}
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
const int B = 560;
//
//int calc(ve<int> a) {
// int ans = 0;
// fr (i, 0, sz(a) - 1) {
// set<int> s;
// fr (j, i, sz(a) - 1) {
// s.insert(a[j]);
// ans += sz(s);
// }
// }
// return ans;
//}
//
//
//ll calc2(ve<int> a) {
// int total = 0;
// fe (x, a) total += x;
// ll ans = 0;
// int toLeft = 0;
// ans += 1LL * sz(a) * total * (total + 1) / 2;
// fr (i, 0, sz(a) - 1) {
// int toRight = total - toLeft - a[i];
// ans -= 1LL * toLeft * (toLeft + 1) / 2;
// ans -= 1LL * toRight * (toRight + 1) / 2;
// toLeft += a[i];
// }
// return ans;
//}
//
//ll calc3Brute(ve<pii> a) {
// assert(sz(a) <= 2 * B);
// int total = 0;
// int gr = 0;
// fe (x, a) {
// total += x.fi * x.se;
// gr += x.se;
// }
// ll ans = 0;
//
// ans += 1LL * gr * total * (total + 1) / 2;
// int toLeft = 0;
// fe (cur, a) {
// fr (j, 1, cur.se) {
// ans -= 1LL * toLeft * (toLeft + 1) / 2;
// toLeft += cur.fi;
// }
// }
// reverse(all(a));
// toLeft = 0;
// fe (cur, a) {
// fr (j, 1, cur.se) {
// ans -= 1LL * toLeft * (toLeft + 1) / 2;
// toLeft += cur.fi;
// }
// }
// return ans;
//}
ll calc3(ve<pll> a) {
assert(sz(a) <= 2 * B);
ll total = 0;
ll gr = 0;
fe (x, a) {
total += x.fi * x.se;
gr += x.se;
}
ll ans = 0;
ans += 1LL * gr * total * (total + 1) / 2;
ll toLeft = 0;
fe (cur, a) {
ll res = 0;
res += toLeft * cur.se;
res += cur.fi * 1LL * cur.se * (cur.se - 1) / 2;
res += 1LL * toLeft * toLeft * cur.se;
{
ll t = cur.se * (cur.se - 1) / 2;
t *= 2;
res += t * cur.fi * toLeft;
}
cur.se--;
ll sumSquares = cur.se * (cur.se + 1) * (2 * cur.se + 1) / 6;
cur.se++;
res += sumSquares * cur.fi * cur.fi;
res /= 2;
ans -= res;
toLeft += cur.fi * cur.se;
}
reverse(all(a));
toLeft = 0;
fe (cur, a) {
ll res = 0;
res += toLeft * cur.se;
res += cur.fi * 1LL * cur.se * (cur.se - 1) / 2;
res += 1LL * toLeft * toLeft * cur.se;
{
ll t = cur.se * (cur.se - 1) / 2;
t *= 2;
res += t * cur.fi * toLeft;
}
cur.se--;
ll sumSquares = cur.se * (cur.se + 1) * (2 * cur.se + 1) / 6;
cur.se++;
res += sumSquares * cur.fi * cur.fi;
res /= 2;
ans -= res;
toLeft += cur.fi * cur.se;
}
return ans;
}
const int N = 6e5 + 5;
int n, q;
int a[N];
int cnt[N];
int rnd(int l, int r) {
return rng() % (r - l + 1) + l;
}
//ll solve(ve<int> a) {
// fe (x, a) cnt[x] = 0;
//
// fe (x, a) cnt[x]++;
//
// ve<pii> order;
// fe (x, a) {
// if (cnt[x]) {
// order.pb({cnt[x], x});
// cnt[x] = 0;
// }
// }
// sort(all(order));
// reverse(all(order));
//
// {
// ve<pii> st;
// fe (cur, order) {
// if (!sz(st) || cur.fi != st.back().fi) {
// st.pb({cur.fi, 1});
// } else {
// st.back().se++;
// }
// }
// deque<pii> d;
// bool who = 0;
// fe (x, st) {
// if (x.se > 1) {
// d.push_front({x.fi, x.se / 2});
// d.pb({x.fi, x.se / 2});
// x.se %= 2;
// }
// if (x.se) {
// if (who == 0) {
// if (sz(d) && d.front().fi == x.fi) d.front().se++;
// else d.push_front({x.fi, 1});
// } else {
// if (sz(d) && d.back().fi == x.fi) d.back().se++;
// else d.pb({x.fi, 1});
// }
// who ^= 1;
// }
// }
//
// ve<pll> v;
// ve<pii> v2;
// fe (x, d) {
// v.pb(x);
// v2.pb(x);
// }
//
//// cout << calc3Brute(v2) << "\n";
//
// return calc3(v);
// }
// assert(0);
//}
ve<array<int, 3>> Q;
set<int> have;
int cnt2[N];
ll ans[N];
int toUpd[N];
int szToUpd;
void add(int x) {
cnt2[cnt[x]]--;
if (cnt2[cnt[x]] == 0) {
toUpd[szToUpd++] = cnt[x];
// have.erase(cnt[x]);
}
cnt[x]++;
cnt2[cnt[x]]++;
if (cnt2[cnt[x]] == 1) {
toUpd[szToUpd++] = cnt[x];
// have.insert(cnt[x]);
}
}
void del(int x) {
cnt2[cnt[x]]--;
if (cnt2[cnt[x]] == 0) {
toUpd[szToUpd++] = cnt[x];
// have.erase(cnt[x]);
}
cnt[x]--;
cnt2[cnt[x]]++;
if (cnt2[cnt[x]] == 1) {
toUpd[szToUpd++] = cnt[x];
// have.insert(cnt[x]);
}
}
ll getAns() {
ve<pii> st;
fe (cur, have) {
st.pb({cur, cnt2[cur]});
}
reverse(all(st));
deque<pii> d;
bool who = 0;
fe (x, st) {
if (x.se > 1) {
d.push_front({x.fi, x.se / 2});
d.pb({x.fi, x.se / 2});
x.se %= 2;
}
if (x.se) {
if (who == 0) {
if (sz(d) && d.front().fi == x.fi) d.front().se++;
else d.push_front({x.fi, 1});
} else {
if (sz(d) && d.back().fi == x.fi) d.back().se++;
else d.pb({x.fi, 1});
}
who ^= 1;
}
}
ve<pll> v;
fe (x, d) {
v.pb(x);
}
return calc3(v);
}
bool check[N];
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(0);
cin.tie(0);
#endif
// cout << 3e5 * sqrt(3e5) * 9 / 1e8 << "\n";
//
// return 0;
cin >> n >> q;
fr (i, 1, n) {
cin >> a[i];
}
fr (i, 1, q) {
int l, r;
cin >> l >> r;
Q.pb({l, r, i});
}
sort(all(Q), [](array<int, 3> a, array<int, 3> b) {
if (a[0] / B != b[0] / B) {
return a[0] / B < b[0] / B;
}
return a[1] < b[1];
});
int L = 1;
int R = 0;
fe (cur, Q) {
while (R < cur[1]) add(a[++R]);
while (L > cur[0]) add(a[--L]);
while (R > cur[1]) del(a[R--]);
while (L < cur[0]) del(a[L++]);
fr (i, 0, szToUpd - 1) {
if (!check[toUpd[i]]) {
check[toUpd[i]] = 1;
int x = toUpd[i];
if (cnt2[x] == 0) {
have.erase(x);
} else {
have.insert(x);
}
}
}
fr (i, 0, szToUpd - 1) {
check[toUpd[i]] = 0;
}
szToUpd = 0;
ans[cur[2]] = getAns();
}
fr (i, 1, q) {
cout << ans[i] << "\n";
}
return 0;
}
