#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 300000, K = 400;
uint32_t a[N], freq[N];
uint64_t ans[N];
tuple<size_t, size_t, size_t> queries[N];
inline uint64_t gauss(uint64_t n) { return (n * (n + 1)) / 2; }
inline uint64_t range_gauss(uint64_t a, uint64_t b)
{
return gauss(b) - (a ? gauss(a - 1) : 0);
}
inline uint64_t sum_of_squares(uint64_t n) { return (n * (n + 1) * ((n << 1) + 1)) / 6; }
uint64_t range_cost(uint64_t l0, uint64_t y, uint64_t z, uint64_t n)
{
return -range_gauss(l0, l0 + z * y - 1) - z * l0 * l0 - 2 * l0 * y * gauss(z - 1) -
y * y * sum_of_squares(z - 1) + z * n * (l0 + y) + y * n * gauss(z - 1);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t n, q;
cin >> n >> q;
for (size_t i = 0; i < n; ++i)
cin >> a[i], --a[i];
for (size_t i = 0; i < q; ++i)
cin >> get<0>(queries[i]) >> get<1>(queries[i]), --get<0>(queries[i]), --get<1>(queries[i]),
get<2>(queries[i]) = i;
sort(queries, queries + q, [](auto const &a, auto const &b)
{ return get<0>(a) / K == get<0>(b) / K ? get<1>(a) < get<1>(b) : get<0>(a) < get<0>(b); });
map<size_t, size_t> freq_of_freq;
size_t i = 0, j = 0;
freq[a[0]] = 1;
freq_of_freq[1] = 1;
for (size_t k = 0; k < q; ++k)
{
auto const [u, v, qi] = queries[k];
while (j < v)
{
++j;
freq[a[j]]++;
freq_of_freq[freq[a[j]] - 1]--;
freq_of_freq[freq[a[j]]]++;
}
while (i > u)
{
--i;
freq[a[i]]++;
freq_of_freq[freq[a[i]] - 1]--;
freq_of_freq[freq[a[i]]]++;
}
while (j > v)
{
freq_of_freq[freq[a[j]]]--;
freq_of_freq[freq[a[j]] - 1]++;
freq[a[j]]--;
--j;
}
while (i < u)
{
freq_of_freq[freq[a[i]]]++;
freq_of_freq[freq[a[i]] - 1]--;
freq[a[i]]++;
--i;
}
uint64_t lsum = 0, rsum = 0, cost = 0;
for (auto const &[freq, num] : freq_of_freq)
if (freq)
{
size_t num_left, num_right;
if (lsum < rsum)
num_right = num / 2, num_left = num - num_right;
else
num_left = num / 2, num_right = num - num_left;
cost += range_cost(lsum, freq, num_left, v - u + 1);
cost += range_cost((v - u + 1) - rsum - num_right * freq, freq, num_right, v - u + 1);
lsum += num_left * freq;
rsum += num_right * freq;
}
ans[qi] = cost;
}
for (size_t i = 0; i < q; ++i)
cout << ans[i] << '\n';
}
