Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, ..., aj.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).
• Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
• In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

Output

• For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, ..., aj in a single line.

   

Example

Input51 1 2 1 331 52 43 5Output323 

#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define CLR(arr,val) memset(arr,val,sizeof(arr))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair<int,int> pii;typedef long long LL;const double PI=acos(-1.0);const int N=30010;struct seg{    int lson,rson;    int cnt;};seg T[N*20];int root[N],tot;vector<int>pos;int arr[N];int last_pos[N];void init(){    pos.clear();    CLR(root,0);    tot=0;    T[0].cnt=T[0].lson=T[0].rson=0;    CLR(last_pos,0);}void update(int &cur,int ori,int l,int r,int pos,int flag){    cur=++tot;    T[cur]=T[ori];    T[cur].cnt+=flag;    if(l==r)        return ;    int mid=MID(l,r);    if(pos<=mid)        update(T[cur].lson,T[ori].lson,l,mid,pos,flag);    else        update(T[cur].rson,T[ori].rson,mid+1,r,pos,flag);}int query(int S,int E,int l,int r,int x,int y){    if(x<=l&&r<=y)        return T[E].cnt-T[S].cnt;    else    {        int mid=MID(l,r);        if(y<=mid)            return query(T[S].lson,T[E].lson,l,mid,x,y);        else if(x>mid)            return query(T[S].rson,T[E].rson,mid+1,r,x,y);        else            return query(T[S].lson,T[E].lson,l,mid,x,mid)+query(T[S].rson,T[E].rson,mid+1,r,mid+1,y);    }}int main(void){    int n,m,i,l,r;    while (~scanf("%d",&n))    {        init();        for (i=1; i<=n; ++i)        {            scanf("%d",&arr[i]);            pos.push_back(arr[i]);        }        scanf("%d",&m);        sort(pos.begin(),pos.end());        pos.erase(unique(pos.begin(),pos.end()),pos.end());        int temp_rt=0;        for (i=1; i<=n; ++i)        {            arr[i]=lower_bound(pos.begin(),pos.end(),arr[i])-pos.begin()+1;            if(!last_pos[arr[i]])            {                update(root[i],root[i-1],1,n,i,1);                last_pos[arr[i]]=i;            }            else            {                update(temp_rt,root[i-1],1,n,last_pos[arr[i]],-1);                update(root[i],temp_rt,1,n,i,1);                last_pos[arr[i]]=i;            }        }        for (i=0; i<m; ++i)        {            scanf("%d%d",&l,&r);            printf("%d\n",query(root[l-1],root[r],1,n,l,r));        }    }    return 0;}