#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <climits>
#include <cmath> 

// using reference intervals [x,y) with  (x, y) = (d i , d j) where d = ceil[sqrt(n)]


using namespace std;


template <typename T>
void print(vector<T> &a) {
    for (auto e: a) {
	cout << e << " ";
    }
    cout << "\n";
}


struct interval {
    int l;
    int r;
    int k;
    int result;
};

void print_i(const interval &e) {
    cout << e.l << " " << e.r << " " << e.k << " " << e.result << "\n";
}




int update_left_up(vector<int> &multiset, vector<int>&c, int froml, int tol) {
    int delta =0;
    int l = froml;
    while (l < tol) {
	--multiset[c[l]];
	if (multiset[c[l]] == 0) {
	    --delta;
	}
	++l;
    }
    return delta;
}

int update_left_down(vector<int> &multiset, vector<int>&c, int froml, int tol) {
    int delta = 0;
    int l = froml - 1;
    while (l >= tol) {
	++multiset[c[l]];
	if (multiset[c[l]] == 1) {
	    ++delta;
	}
	--l;
    }
    return delta;
}

int update_right_up(vector<int> &multiset, vector<int>&c, int fromr, int tor) {
    int delta = 0;
    int r = fromr;
    while (r < tor) {
	++multiset[c[r]];
	if (multiset[c[r]] == 1) {
	    ++delta;
	}
	++r;
    }
    return delta;
}

int update_right_down(vector<int> &multiset, vector<int>&c, int fromr, int tor) {
    int delta = 0;
    int r = fromr - 1;
    while (r >= tor) {
	--multiset[c[r]];
	if (multiset[c[r]] == 0) {
	    --delta;
	}
	--r;
    }
    return delta;
}


    
    

int update(vector<int> &multiset, vector<int> &c, const interval& from, const interval& to) {
    int delta = 0;
    if (to.r >= from.r) {
	delta += update_right_up(multiset, c, from.r, to.r);
	if (to.l >= from.l) {
	    delta += update_left_up(multiset, c, from.l, to.l);
	} else {
	    delta += update_left_down(multiset, c, from.l, to.l);
	}
    } else {
	if (to.l >= from.l) {
	    delta += update_left_up(multiset, c, from.l, to.l);
	} else {
	    delta += update_left_down(multiset, c, from.l, to.l);
	}
	delta += update_right_down(multiset, c, from.r, to.r);
    }
    return delta;
}
	



int main() {
    int n, q;
    cin >> n >> q;

    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
	cin >> c[i];
    }

    int d = (int)(sqrt(double(n))) + 1;
    int irange = (n - 1) / d + 1;
    int jrange = irange;
    

    vector<vector<vector<interval>>> data (irange, vector<vector<interval>>(irange, vector<interval> {}));

    for (int i = 0; i < irange; ++i) {
	for (int j = i; j < jrange; ++j) {
	    interval temp;
	    temp.l = i*d;
	    temp.r = j*d;
	    temp.k = -1;
	    temp.result = (i == j) ? 0 : INT_MIN;
	    data[i][j].push_back(temp);
	}
    }
	    

    for (int k = 0; k < q; ++k) {
	int l, r;
	cin >> l >> r;
	--l;  // count from 0, include left boundary, don't include right boundary of each interval
	int i = l / d;
	int j = r / d;
	interval temp;
	temp.l = l;
	temp.r = r;
	temp.k = k;
	temp.result = INT_MIN;
	data[i][j].push_back(temp);
    }

    for (int i = 0; i < irange; ++i) {
	vector<int> multiset(n+1);
	for (int j = i; j < jrange; ++j) {
	    int a = 1;
	    while (a < data[i][j].size()) {
		int delta = update(multiset, c, data[i][j][a-1], data[i][j][a]);
		data[i][j][a].result = data[i][j][a-1].result + delta;
		++a;
	    }
	    if (j + 1 < jrange) {
		int delta = update(multiset, c, data[i][j][a-1], data[i][j+1][0]);
		data[i][j+1][0].result = data[i][j][a-1].result + delta;
	    }
	}
    }

    vector<int> results(q);
    
    for (int i = 0; i < irange; ++i) {
	for (int j = 0; j < irange; ++j) {
	    //cout << "i " << i << ", j " << j << ":\n";
	    for (int a = 1; a < data[i][j].size(); ++a) {
		results[data[i][j][a].k] = data[i][j][a].result;
	    }
	}
    }

    for (auto e: results) {
	cout << e << "\n";
    }
    
}
	
	


Measured memory_bytes: 40000