DQUERY - D-query

DQUERY - D-query

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

Input
5
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3 

----------------------------------------code-------------------------------------------------------------#include<iostream>
#include<bits/stdc++.h>
using namespace std;
  int ans=0;
struct node
 {
   int x,y,index;
   
 } qry[1000000];
 
  int bck_sz=441;
   int result[1000000];
    int has[10000000];
    int arr[10000000];
 
 int read_int(){
 char r;
 bool start=false,neg=false;
  int ret=0;
 while(true){
  r=getchar();
  if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
   continue;
  }
  if((r-'0'<0 || r-'0'>9) && r!='-' && start){
   break;
  }
  if(start)ret*=10;
  start=true;
  if(r=='-')neg=true;
  else ret+=r-'0';
 }
 if(!neg)
  return ret;
 else
  return -ret;
}

 bool compare(node a,node b)
{
    int i,j;
    i=a.x/bck_sz;
    j=b.x/bck_sz;
    if(i==j)
    {
        if(a.y<b.y)
            return 1;
        else
            return 0;
    }
    else{
        if(i<j)
            return 1;
        else
            return 0;
    }
}

int join(int num)
 {
   //cout<<" join "<<num<<"ans is "<<ans<<endl;
  has[num]++;
  if(has[num]==1) ans++;
 // cout<<" join "<<num<<"ans is "<<ans<<endl;
  
 }
 
 int  del(int num)
  {
   
    has[num]--;
    if(has[num]==0) ans--;
    //cout<<"del "<<num<<" ans is "<<ans<<endl;
  }
  
 int main()
  {
    int n;
     cin>>n;
      for(int i=0;i<n;i++)
      arr[i]=read_int();
       int q;
        cin>>q;
        for(int i=0;i<q;i++)
         {
           int a,b;
            a=read_int();
            b=read_int();
              //cin>>a>>b;
              a-=1;
              b-=1;
              qry[i].x=a;
              qry[i].y=b;
              qry[i].index=i;
              
   }
   
   sort(qry,qry+q,compare);
   int l=0,r=-1;
   
   for(int i=0;i<q;i++)
    {
      int x=qry[i].x;
      int y=qry[i].y;
     //  cout<<" query in the range "<<x<<" "<<y<<endl;
      int index=qry[i].index;
      while(r<y)
                   {

                       r++;
                           // cout<<"r "<<r<<endl;
                        join(arr[r]);
                          }
                          
              while(l>x)
                {
                   l--;
                  join(arr[l]);
                  }
    while(l<x)
    {
        del(arr[l]);
        l++;
    }
    while(r>y)
    {
        del(arr[r]);
        r--;
    }
    
    result[index]=ans;
    
    }
    for(int i=0;i<q;i++) printf("%d\n",result[i]);
  }