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
sahil_1994:
20171014 21:02:40
Hint for solving using segment tree(offline).


Shubham Gupta:
20171012 11:49:45
Remember to use scanf/printf instead of cin/cout.


pradeepgangwar:
20171009 15:35:58
My 100th. Mo's Algorithm does it :) 

the_phoenixx:
20171008 23:14:45
use scanf/printf only....


vishesh197:
20171006 19:17:47
solved it using MO's algorithm and frequency array........AC in second go..0.40 sec.I tried to solve it using segment tree too but was'nt able to solve it.Can anybody suggest a solution with segment tree? 

prabhat236218:
20171001 15:58:53
@sdibt1 please help me how you did it


prabhat236218:
20170929 18:53:36
i am also getting TLE in java solution using MO's algo and fenwick tree also..... help me....what should i do


hitman007:
20170924 16:07:11
Has anyone solved it in Java using MO algorithm ? I am constantly getting TLE despite using fast I/O. 

sirjan13:
20170909 20:32:52
Used Mo's Algorithm:


madhavgaba:
20170827 20:20:56
spinning around segment tree proves really tough sometimes, collect gems like MO's algo :) 
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 