#include <bits/stdc++.h>
using namespace std;
//loops (warning : long long)
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r - 1); i >= l; --i)
//pairs, tuples
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
//vectors
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sum_of(v) accumulate(all(v), 0ll)
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
//binary search
#define lwb lower_bound
#define upb upper_bound
//other stuffs
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int f(const vi& a, int max_value){ //a[i] \in [0, max_value)
int cnt = 0;
vi check(max_value);
FOR(i, 0, sz(a)){
int cur = 0;
stack<int> st;
FOR(j, i, sz(a)){
if(!check[a[j]]) ++cur, check[a[j]] = true, st.push(a[j]);
cnt += cur;
}
while(!st.empty()){
check[st.top()] = false;
st.pop();
}
}
return cnt;
}
int g(const vi& a){ //cnt array
int sum = 0;
FOR(i, 0, sz(a)){
int x = a[i];
sum += x * (x + 1) / 2;
FOR(j, i + 1, sz(a)){
sum += x * a[j] * (j - i + 1);
}
}
return sum;
}
void gen(){
vi trick = {1, 1, 2};
int best = 1e9;
vector<vi> all_ok;
do{
int cur = g(trick);
if(minimize(best, cur)) all_ok = {trick};
else if(best == cur) all_ok.pb(trick);
} while(next_permutation(all(trick)));
cout << best << '\n';
for(auto vec : all_ok){
for(auto it : vec) cout << it << ' '; cout << '\n';
}
return;
// // vi a = {1, 2, 1, 3, 2, 3, 1, 3, 3};
// vi a = {3, 3, 3, 4, 4, 4, 4, 2, 2, 1};
// vi perm(sz(a)); iota(all(perm), 0);
// int cur = 1e9;
// vector<vi> lst;
// do{
// vi ex(sz(a));
// FOR(i, 0, sz(a)) ex[i] = a[perm[i]];
// int tmp = f(ex, 4);
// if(minimize(cur, tmp)){
// lst = {ex};
// } else if(cur == tmp) lst.pb(ex);
// } while(next_permutation(all(perm)));
// cout << cur << '\n';
// sort(all(lst)); compact(lst);
// cout << sz(lst) << '\n';
// for(auto it : lst) {
// for(auto i : it) cout << i << ' '; cout << '\n';
// }
}
ll calc_fast(const vi& cnt){
ll sum_product = 0, sum = 0;
FOR(i, 0, sz(cnt)){
sum_product += 1LL * (i + 1) * cnt[i];
sum += cnt[i];
}
// for(auto u : cnt) cout << u << ' '; cout << '\n';
ll result = 0;
FOR(i, 0, sz(cnt)){
result += 1LL * cnt[i] * (cnt[i] + 1) / 2;
sum_product -= 1LL * (i + 1) * cnt[i];
sum -= cnt[i];
result += 1LL * cnt[i] * (sum_product - sum * i);
}
return result;
}
void testcase(int ntestcase){
int N, Q;
cin >> N >> Q;
vi a(N);
FOR(i, 0, N){
cin >> a[i];
}
vi b = a;
sort(all(b)); compact(b);
FOR(i, 0, N) a[i] = lower_bound(all(b), a[i]) - b.begin();
FOR(_, 0, Q){
int l, r;
cin >> l >> r;
--l;
vi cnt(sz(b));
FOR(i, l, r){
++cnt[a[i]];
}
sort(all(cnt));
vi odd, even;
FOR(i, 0, sz(cnt)){
if(i & 1){
if(cnt[i]) odd.pb(cnt[i]);
} else{
if(cnt[i]) even.pb(cnt[i]);
}
}
reverse(all(even));
vi result = odd;
result.insert(result.end(), all(even));
cout << calc_fast(result) << '\n';
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif // LOCAL
// gen();
// return 0;
int T = 1;
// cin >> T;
FOR(i, 0, T) testcase(i);
return 0;
}
