#include<bits/stdc++.h>
using namespace std;

#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define FO(i, j) FOR(i, 0, j, 1)
#define RFO(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define mp make_pair
#define pb push_back
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define ps(x,y) fixed<<setprecision(y)<<x //cout << ps(ans, decimal places);
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
typedef pair<int, int> pi;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<string> vs;
typedef vector<pi> vpii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef map<int,int> mi;
typedef map<long long,long long> ml;
typedef set<int> si;
typedef set<long long> sl;
typedef long long int ll;
typedef unsigned long long int  ull;
typedef priority_queue<ll> mxhpl;
typedef priority_queue<int> mxhpi;
typedef priority_queue<ll, vector<ll>, greater<ll>> mnhpl;
typedef priority_queue<int, vector<int>, greater<int>> mnhpi;

void IO() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
#endif
}

template<typename... T>
void read(T&... args) {
  ((cin >> args), ...);
}

template<typename... T>
void write(T&&... args) {
  ((cout << args << " "), ...);
}

#define MOD 1000000007
int mpow(int, int);
/*******************************************************/

const int I = 0, Q = 1;

class Info {
public:
  int type, l, r, i, val, end;
  Info() {
    type = l = r = i = val = end = -1;
  }
};

int n, m,sgt[70000] = {0};
//  a[30001],
vector<Info> qs;
unordered_map<int,int> occ;

int comp_ends(const Info& a, const Info& b) {
  if (a.type == b.type) {
    if (a.type == Q) return a.r <= b.r;
    return a.i <= b.i;
  } else {
    if (a.type == Q) return a.r < b.i;
    return a.i <= b.r;
  }
}

void insert(int i, int val, int l, int r, int pos) {
  if (l == r && l == i) {
    sgt[pos] = val;
    return;
  }
  else if (l == r || l > i || i > r) return;
  int mid = (l+r)/2;
  if (mid < i) insert(i,val,mid+1,r,pos*2+2);
  else insert(i,val,l,mid,pos*2+1);

  sgt[pos] = sgt[pos*2+2]+sgt[pos*2+1];
}

int query(int low, int high, int l, int r, int pos) {
  if (low <= l && high >= r) return sgt[pos];
  else if (low > r || high < l) return 0;

  int mid = (r+l)/2;
  int ans = query(low,high,l,mid,pos*2+1);
  ans += query(low,high,mid+1,r,pos*2+2);

  return ans;
}

void solve() {
  read(n);
  FO(i,n) {
    Info tmp;
    tmp.type = I;
    read(tmp.val);
    tmp.i = i;
    tmp.end = i;
    qs.pb(tmp);
  }

  read(m);
  FO(i, m) {
    Info tmp;
    tmp.type = Q;
    read(tmp.l, tmp.r);
    tmp.l--;
    tmp.r--;
    tmp.i = i;
    tmp.end = tmp.r;
    qs.pb(tmp);
  }

  sort((qs).begin(), (qs).end(), comp_ends);

  int ans[m];

  for(auto x: qs) {
    // write(x.type, x.r, x.i, "\n");
    if (x.type) {
      ans[x.i] = query(x.l,x.r,0,n-1,0);

    } else {
      if (occ.find(x.val) != occ.end()){
        insert(x.i,1,0,n-1,0);
        insert(occ[x.val],0,0,n-1,0);
        occ[x.val] = x.i;

      } else {
        insert(x.i,1,0,n-1,0);
        occ[x.val] = x.i;

      }
    }
  }

  FO(i,m) cout << ans[i] << "\n";
  // FO(i,m+n) write(qs[i].type?qs[i].r:qs[i].i);
}

int main() {
  IO();

  int t = 1;
  // cin >> t;
  while(t--) {
    solve();
  }

  return 0;
}

/*******************************************************/
int mpow(int base, int exp) {
  base %= MOD;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % MOD;
    base = ((ll)base * base) % MOD;
    exp >>= 1;
  }
  return result;
}