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
SHASHANK GUPTA:
20170108 12:14:00
If getting TLE even after [MO+fast I/O] , use struct (instead of pair) and even after this also you get TLE , look your comparator function. 

adityaghosh96:
20170103 04:50:00
O(n*sqrt(n)) with scanf,printf. 

harisagar:
20161228 09:57:28
use faster io(not cin,cout)............. Last edit: 20161228 09:58:05 

rihaz_zahir:
20161228 09:21:22
std::ios_base::sync_with_stdio(false);


hamjosh1:
20161227 21:41:18
fast io to use in cpp 

vengatesh15:
20161222 17:08:02
my first MO type Problem AC after 3WA 

testing java:
20161213 12:58:03
Nice problem, not so nice time limit. Wasted a lot of time on making java solution fast enough. 

rihaz_zahir:
20161205 09:32:01
where can i find my previous submission for this question? 

davidgalehouse:
20161115 05:44:54
0.17s with C++, TLE with C# despite very similar benchmarking on my local machine for a 30k/200k test case... I don't get how, given other ACs with much higher times like .5 or .7... Also the source array is malformed, you'll have to trim before splitting or remove empty entries if trying C#. Last edit: 20161115 05:47:16 

oakszyjrnrdy:
20161026 15:59:26
It's very easy to solve this problem using a data structure called 'Zhuxi Tree' in Chinese(sorry~, i don't know how to call it in English, maybe Chair Tree?).

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 