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
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?).


vicennial:
20161024 19:20:21
How are people solving it with 0.3+ running time when the time limit itself is 0.227 seconds?? 

shubh809:
20161019 18:56:29
Last edit: 20161110 12:28:48 

blackops:
20161014 06:00:22
Persistent seg tree takes 0.28s…………;


kk786:
20161007 13:44:14
nice problem!


imwrkhrd:
20160828 01:42:17
Be aware, n is probably bigger than 30000 

advanced:
20160819 19:32:00
learnt something new and amazing 

sieunhanbom04:
20160807 07:57:09
cin and cout gave me TLE. printf and scanf fix it. 
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 