#pragma GCC optimize ("O3,unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; const int BLOCK_SIZE = 550; 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]; map <int, int> mp; 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; for (auto x : mp) { 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"; }