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
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
beaware n is deffinately >300000. Last edit: 20161019 18:56: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. 

Advitiya:
20160806 13:55:06
BIT0.27s


askerov5555:
20160804 22:22:21
I got AC with 0.4 second. With O(qlog(q) + qlog(n)) and scanf. Last edit: 20160804 22:23:18 
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 