#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxN = 300'000;
const int maxQ = 50'000;
const int Sp = (1 << 19); //******
struct fenwick_tree
{
vector<long long> BIT = vector<long long>(1+Sp, 0);
void add(int L, int i, long long v)
{
for(int j = i; j <= Sp; j += j&-j)
BIT[j] += v;
}
int rangesum(int L, int i)
{
long long res = 0;
for(int j = i; j >= 1; j -= j&-j)
res += BIT[j];
return res;
}
};
struct segtree
{
int l;
int r;
long long lp = 0;
long long sm = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void add(int L, int R, long long V)
{
if(R < L) return;
if(R < l || r < L) return;
else if(L <= l && r <= R)
{
lp += V;
sm += (r-l+1)*V;
}
else
{
sm += V*(min(R,r) - max(L,l) + 1);
left->add(L, R, V);
right->add(L, R, V);
}
}
long long rangesum(int L, int R)
{
if(R < L) return 0;
if(R < l || r < L) return 0;
else if(L <= l && r <= R)
{
return sm;
}
else
{
return lp*(min(R,r) - max(L,l) + 1) + left->rangesum(L, R) + right->rangesum(L, R);
}
}
};
vector<int> a(1+maxN);
vector<int> l(1+maxQ), r(1+maxQ);
int L = 1;
int R = 0;
fenwick_tree ST;
segtree ST2(1, Sp);
segtree ST3(1, Sp);
vector<int> species_size(1+Sp);
vector<int> species_rank(1+Sp); //1 = center, S = edge
vector<int> rank_species(1+Sp);
vector<int> rank_pos(1+Sp);
vector<int> pos_rank(1+Sp);
vector<int> size_lowrank(1+maxN, -1), size_highrank(1+maxN, -1);
long long curr_ans = 0;
void add(int A)
{
// cerr << "add " << A << '\n';
int curr_size = species_size[A];
// cerr << "curr_size = " << curr_size << '\n';
int B = rank_species[ size_lowrank[ curr_size ] ];
swap(rank_species[ species_rank[A] ], rank_species[ species_rank[B] ]);
swap(species_rank[A], species_rank[B]);
long long T = species_size[A];
long long P = ST.rangesum(1, rank_pos[species_rank[A]] - 1);
long long S = R-L+1 - P - T;
curr_ans += ((T+1)*(T+2)/2) - (T*(T+1)/2);
curr_ans += 2*P + 2*S;
curr_ans += ST2.rangesum(1, rank_pos[species_rank[A]] - 2);
curr_ans += ST3.rangesum(rank_pos[species_rank[A]] + 2, Sp);
// cerr << "A = " << A << '\n';
species_size[A]++;
long long RP = rank_pos[ species_rank[A] ];
ST.add(RP, RP, +1);
ST2.add(RP, Sp, +1);
ST3.add(1, RP, +1);
if(size_lowrank[curr_size+1] > size_highrank[curr_size+1])
{
// cerr << "creating new\n";
size_lowrank[curr_size+1] = size_highrank[curr_size+1] = size_lowrank[curr_size];
size_lowrank[curr_size]++;
}
else
{
// cerr << "expanding old\n";
size_highrank[curr_size+1]++;
size_lowrank[curr_size]++;
}
}
void remove(int A)
{
// cerr << "remove " << A << '\n';
int curr_size = species_size[A];
int B = rank_species[ size_highrank[ curr_size ] ];
swap(rank_species[ species_rank[A] ], rank_species[ species_rank[B] ]);
swap(species_rank[A], species_rank[B]);
species_size[A]--;
int RP = rank_pos[ species_rank[A] ];
ST.add(RP, RP, -1);
ST2.add(RP, Sp, -1);
ST3.add(1, RP, -1);
long long T = species_size[A];
long long P = ST.rangesum(1, rank_pos[species_rank[A]] - 1);
long long S = R-L+1 - P - T;
curr_ans -= ((T+1)*(T+2)/2) - (T*(T+1)/2);
curr_ans -= 2*P + 2*S;
curr_ans -= ST2.rangesum(1, rank_pos[species_rank[A]] - 2);
curr_ans -= ST3.rangesum(rank_pos[species_rank[A]] + 2, Sp);
if(size_lowrank[curr_size-1] > size_highrank[curr_size-1])
{
size_lowrank[curr_size-1] = size_highrank[curr_size-1] = size_highrank[curr_size];
size_highrank[curr_size]--;
}
else
{
size_lowrank[curr_size-1]--;
size_highrank[curr_size]--;
}
}
int C;
const int rt = 700;
void fastscan(int &number)
{
bool negative = false;
int c;
number = 0;
c = getchar();
if (c=='-')
{
negative = true;
c = getchar();
}
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
if (negative)
number *= -1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, Q;
fastscan(N);
fastscan(Q);
for(int i = 1; i <= N; i++) fastscan(a[i]);
for(int j = 1; j <= Q; j++)
{
fastscan(l[j]);
fastscan(r[j]);
}
vector<long long> answer(1+Q);
vector<int> queries(Q);
for(int j = 0; j < Q; j++) queries[j] = j+1;
sort(queries.begin(), queries.end(), [] (int u, int v)
{
if(l[u] / rt != l[v] / rt) return l[u] / rt < l[v] / rt;
else return r[u] < r[v];
});
L = 1;
R = 0;
for(int s = 1; s <= Sp; s++)
{
species_size[s] = 0;
species_rank[s] = s;
rank_species[s] = s;
}
C = (1+Sp)/2;
if(Sp % 2 == 0)
C++;
vector<int> P(Sp);
for(int i = 0; i < Sp; i++) P[i] = i+1;
sort(P.begin(), P.end(), [] (int u, int v)
{
if(abs(u - C) != abs(v - C)) return abs(u - C) < abs(v - C);
else return u < v;
});
for(int i = 1; i <= Sp; i++)
{
rank_pos[i] = P[i-1];
pos_rank[ P[i-1] ] = i;
}
size_lowrank[0] = 1;
size_highrank[0] = Sp;
for(int i = 1; i <= N; i++)
{
size_lowrank[i] = -1;
size_highrank[i] = -2;
}
L = l[queries[0]];
R = L-1;
for(int j: queries)
{
while(R < r[j])
{
add(a[R+1]);
R++;
}
while(r[j] < R)
{
R--;
remove(a[R+1]);
}
while(l[j] < L)
{
add(a[L-1]);
L--;
}
while(L < l[j])
{
L++;
remove(a[L-1]);
}
answer[j] = curr_ans;
}
for(int j = 1; j <= Q; j++) cout << answer[j] << '\n';
}
