range unique value find with offline query

intput:
4
1 2 3 3
2
1 3
3 4
output:3 1


#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const ll mx = 2e5 + 100;
ll tree[mx * 3];
int arr[mx * 3];

void build(ll id, ll b, ll e) {
    if (b == e) {
        tree[id] = arr[b];
        return;
    }
    int mid = (b + e) >> 1;
    build(2 * id, b, mid);
    build(2 * id + 1, mid + 1, e);
    tree[id] = tree[id * 2] + tree[id * 2 + 1];
}

void update(ll id, ll b, ll e, ll i, ll val) {
    if (e < i || b > i) {
        return;
    }
    if (e == i && b == i) {
        tree[id] = val;
        return;
    }
    ll mid = (b + e) >> 1;
    update(2 * id, b, mid, i, val);
    update(2 * id + 1, mid + 1, e, i, val);
    tree[id] = tree[id * 2] + tree[id * 2 + 1];
}

ll query(ll id, ll b, ll e, ll i, ll j) {
    if (b > j || e < i) {
        return 0;
    }
    if (i <= b && j >= e) {
        return tree[id];
    }
    ll mid = (b + e) >> 1;
    ll left = query(id * 2, b, mid, i, j);
    ll right = query(id * 2 + 1, mid + 1, e, i, j);
    return left + right;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int a[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int q;
    cin >> q;
    vector<pair<int, int>> vec[n + 1];
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        vec[r].push_back({l, i});
    }
    memset(arr, 0, sizeof(arr));
    build(1, 1, n);
    map<int, int> mp;
    ll ans[n + 1] = {0};
    for (int i = 1; i <= n; i++) {
        if (mp.find(a[i]) == mp.end()) {
            update(1, 1, n, i, 1);
        } else {
            update(1, 1, n, mp[a[i]], 0);
            update(1, 1, n, i, 1);
        }
        mp[a[i]] = i;
        for (auto x:vec[i]) {
            int l = x.first;
            int id = x.second;
            ans[id] = query(1, 1, n, l, i);
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << " ";
    }


    return 0;
}