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
ankur314:
20180617 09:05:23
purely MO in 0.34 sec 

ankur_dhir95:
20180616 18:30:41
Use fast I/O if solving with persistent seg tree (costed me a tle) , though normal I/O would work with offline segment tree solution 

horizon121:
20180610 09:24:24
Beware ::


elmer_fudd:
20180510 20:39:15
i try to solve using direct sqrt decomposition but RTE


mrvincy:
20180504 03:08:23
max(n) is 3e5 and not 3e4 

coderslegacy:
20180423 00:44:12
Ac in one go use Mo's Algorithm 

akshatjain02:
20180414 23:22:18
Solved it using both Mo's Algorithm and Offline Segment Tree :') 

ac_traits:
20180411 10:58:55
I set maxN = (int)3e4 + 10 and get AC 

gangchil:
20180329 12:08:47
mo with cin/cout gives tle use printf/scanf instead (.31s)and value of n is probably <= 300010 costed me lots of wa ;) Last edit: 20180331 01:29:59 

da_201501443:
20180306 14:20:28
Can anybody share your code ??

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 