#include "bits/stdc++.h" using namespace std; #define intt long long #define fi first #define se second const intt mxN = 5e5+1; const intt LG = 20; const intt inf = 1e18; intt n, q; vector<intt> a(mxN); map<intt,intt> mp; struct qry { intt l, r, idx; }; vector<qry>qs; intt sz = 800; bool cmp(qry &a, qry &b) { if(a.l / sz == b.l / sz) { return a.r < b.r; } return a.l / sz < b.l / sz; } intt ans; void add(intt x) { if(mp[x] == 2) ans--; mp[x]++; if(mp[x] == 2) ans++; } void remove(intt x) { if(mp[x] == 2) ans--; mp[x]--; if(mp[x] == 2) ans++; } void _() { cin >> n >> q; sz = sqrt(n); for(intt i = 1; i <= n; i++) { cin >> a[i]; } for(intt i = 0; i < q; i++) { intt a, b; cin >> a >> b; qs.push_back({a, b, i}); } sort(qs.begin(), qs.end(), cmp); vector<intt> c(q); intt l = 1, r = 0; for(intt i = 0; i < q; i++) { intt curl = qs[i].l, curr = qs[i].r; // cout << l << " " << r << " : " << curl << " " << curr << endl; while(r < curr) { r++; add(a[r]); } while(l > curl) { l--; add(a[l]); } while(l < curl) { remove(a[l]); l++; } while(r > curr) { remove(a[r]); r--; } c[qs[i].idx] = ans; } for(intt i = 0; i < q; i++) { cout << c[i] << endl; } cout << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("checklist.in", "r", stdin); // freopen("checklist.out", "w", stdout); intt t = 1, buu = 1; // cin >> t; while(t--){ // cout << "Case #" << buu++ << ": "; _(); } }