#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
int solve(vector<int>& cur){
int sum = 0;
for(int i = 0; i < cur.size(); i++){
for(int j = i; j < cur.size(); j++){
set<int> occ;
for(int k = i; k <= j; k++){
occ.insert(cur[k]);
}
sum += occ.size();
}
}
return sum;
}
int32_t main() {
int n,q;
cin>> n >> q;
vector<int>arr(n);
for(int i = 0; i < n; i++){
cin >> arr[i];
}
// construct small-large-small-large... blocks
while(q--){
int l,r;
cin >> l >> r;
l--;r--;
vector<int> cur;
map<int,int> freq;
for(int i = l; i <= r; i++){
freq[arr[i]]++;
}
vector<pii> temp;
for(auto p : freq){
temp.push_back(p);
}
sort(temp.begin(),temp.end(), [](pii a, pii b) {
if(a.second == b.second) return a.first < b.first;
return a.second < b.second;
});
vector<int> cur1;
int lo = 0, hi = temp.size()-1;
while(lo <= hi){
for(int i = 0; i < temp[lo].second; i++){
cur1.push_back(temp[lo].first);
}
lo++;
if(lo > hi) break;
for(int i = 0; i < temp[hi].second; i++){
cur1.push_back(temp[hi].first);
}
hi--;
}
vector<int> cur2;
lo = 0, hi = temp.size()-1;
while(lo <= hi){
for(int i = 0; i < temp[hi].second; i++){
cur2.push_back(temp[hi].first);
}
hi--;
if(lo > hi) break;
for(int i = 0; i < temp[lo].second; i++){
cur2.push_back(temp[lo].first);
}
lo++;
}
int sum1 = solve(cur1);
int sum2 = solve(cur2);
int sum = min(sum1,sum2);
cout << sum << endl;
}
}
