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
TP:
20160630 22:29:04
AC with Bit + Sorting + (use printf,scanf). cin,cout and vectors cost me 1 TLE. 

ahmad_gafer:
20160608 04:19:20
AC with BIT+sorting , first submission :D 

kliu31415:
20160605 06:07:05
Mo's algorithm+slow IO is somehow faster than 2D range tree with fast IO... lol 

narutorocks:
20160520 06:56:26
Cheated But LEARNT A NEW ALGORITHM 

proficient:
20160518 15:33:07
Anyone here got AC with bitset + square root decomposition of array (not query / MO)? Couldn't get pass the time limit. My algorithm is O(Q * 2 * sqrt(N)) using bitset and square root decomposition. Tried fast IO, inlining and custom implementation of bitset, still not pass time limit 

fnf:
20160415 16:55:11
NEVER use a <= b in comparators. All comparators must be like a < b. 

kaynaat:
20160402 19:19:05
i have solved this problem with MO's algorithm. but i am unable to figure out how to do this with BIT ? can anybody help me with clear understanding as to why and how one should use BIT ? 

farhad chowdhury:
20160317 21:50:20
Can anyone tell me why i got ac with ".42" time where the time limit is ".227"


Arpan Mukherjee:
20160303 16:16:38
One piece of advice for MO's algorithm.Don't use vector of nested pair. Use structure. Pair did cost me 15 TLEs. 

prateek1985:
20160229 14:23:26
Learned lot of new things but still TLE using segment trees in Java!!! 
Added by:  Duc 
Date:  20081026 
Time limit:  0.227s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JS NODEJS PERL 6 VB.net 
Resource:  © VNOI 