count diff numbers on segments

#include <bits/stdc++.h>
// tiom4eg's precompiler options
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
// IO settings
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0)
// Quick types
#define ll long long
#define ld double
#define ull unsigned long long
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define mi vector <vector <int> >
// Quick functions
#define endl "\n"
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define sz(a) a.size()
#define pb push_back
#define mp make_pair
#define fint(n) int n; cin >> n
#define fstr(s) string s; cin >> s
#define farr(a, n) int a[n]; for (int pog = 0; pog < n; ++pog) cin >> a[pog]
// Quick fors
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
// Pragmas
#pragma GCC optimize("O3,unroll-loops") // let the chaos begin!
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
#pragma GCC comment(linker, "/stack:200000000")
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

struct splitmix64 {
    size_t operator()(size_t x) const {
        static const size_t fixed = chrono::steady_clock::now().time_since_epoch().count();
        x += 0x9e3779b97f4a7c15 + fixed;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
};

int R = 1;

struct segtree {
    vi cnt;
    void init() { cnt.resize(2 * R); }
    void inc(int p) {
        p += R;
        while (p) cnt[p]++, p >>= 1;
    }
    void dec(int p) {
        p += R;
        while (p) cnt[p]--, p >>= 1;
    }
    int rsq(int l, int r) {
        int res = 0;
        l += R, r += R;
        while (l < r) {
            if (l & 1) res += cnt[l];
            if (!(r & 1)) res += cnt[r];
            l = (l + 1) >> 1, r = (r - 1) >> 1;
        }
        if (l == r) res += cnt[l];
        return res;
    }
};

int main() {
    fastIO;
    int n; cin >> n;
    while (R < n) R <<= 1;
    int a[n]; FOR(i, 0, n) cin >> a[i];
    segtree t;
    t.init();
    gp_hash_table <int, int, splitmix64> pos;
    int q; cin >> q;
    vector <pair <int, pii> > qry(q);
    FOR(i, 0, q) {
        int l, r; cin >> l >> r, l--, r--;
        qry[i] = {i, {l, r}};
    }
    stable_sort(all(qry), [](const auto& p1, const auto& p2){ return p1.S.S < p2.S.S; });
    int ans[q]; FOR(i, 0, q) ans[i] = 0;
    int p = 0;
    FOR(i, 0, n) {
        if (pos.find(a[i]) != pos.end()) t.dec(pos[a[i]]);
        pos[a[i]] = i;
        t.inc(pos[a[i]]);
        while (p < q && qry[p].S.S == i) ans[qry[p].F] = t.rsq(qry[p].S.F, qry[p].S.S), p++;
    }
    FOR(i, 0, q) cout << ans[i] << endl;
}