DQUERY  Dquery
English  Vietnamese 
Given a sequence of n numbers a_{1}, a_{2}, ..., a_{n} and a number of dqueries. A dquery is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each dquery (i, j), you have to return the number of distinct elements in the subsequence a_{i}, a_{i+1}, ..., a_{j}.
Input
 Line 1: n (1 ≤ n ≤ 30000).
 Line 2: n numbers a_{1}, a_{2}, ..., a_{n} (1 ≤ a_{i} ≤ 10^{6}).
 Line 3: q (1 ≤ q ≤ 200000), the number of dqueries.
 In the next q lines, each line contains 2 numbers i, j representing a dquery (1 ≤ i ≤ j ≤ n).
Output
 For each dquery (i, j), print the number of distinct elements in the subsequence a_{i}, a_{i+1}, ..., a_{j} in a single line.
Example
Input 5 1 1 2 1 3 3 1 5 2 4 3 5 Output 3 2 3
hide comments
Kishore:
20180213 07:45:41
did anyone do it in java? I did it using MO along with fast I/o but getting TLE 

jatin_tayal:
20180114 18:46:46
don't use pair while using MO , use a structure instead !


karthik1997:
20171229 12:37:02
Cant Believe it . With Fast I/O ,my results are :


chandan kumar:
20171215 08:59:47
Offline BIT with fast I/O  0.10s Last edit: 20171215 09:03:36 

pratham_1:
20171215 08:28:34
BIT  0.17s , MO0.30s , AC ;) 

chandan kumar:
20171215 06:25:15
offline fenwick tree/segment tree 

suraj_:
20171213 07:18:28
thanks!! @tanavya


chachaji_harsh:
20171209 12:53:56
can somebody pls tell why my code is printing unexpectedly wrong output (only sometimes)while my mo's implementation looks all good


tanavya:
20171201 13:08:35
Use ceil(sqrt(Q)) instead of int(sqrt(Q)) to get it to pass!! 

gaurav__404:
20171031 20:59:31
AC in one go ;). Use Mo's Algo(see https://www.hackerearth.com/practice/notes/mosalgorithm/) and scanf / printf instead of cin / cout. 
Added by:  Duc 
Date:  20081026 
Time limit:  0.227s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  © VNOI 