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
narutorocks:
20160520 06:56:26
Cheated But LEARNT A NEW ALGORITHM 

proficient:
20160518 15:33:07
Anyone here got AC with bitset + square root decomposition of array (not query / MO)? Couldn't get pass the time limit. My algorithm is O(Q * 2 * sqrt(N)) using bitset and square root decomposition. Tried fast IO, inlining and custom implementation of bitset, still not pass time limit 

fnf:
20160415 16:55:11
NEVER use a <= b in comparators. All comparators must be like a < b. 

kaynaat:
20160402 19:19:05
i have solved this problem with MO's algorithm. but i am unable to figure out how to do this with BIT ? can anybody help me with clear understanding as to why and how one should use BIT ? 

farhad chowdhury:
20160317 21:50:20
Can anyone tell me why i got ac with ".42" time where the time limit is ".227"


Arpan Mukherjee:
20160303 16:16:38
One piece of advice for MO's algorithm.Don't use vector of nested pair. Use structure. Pair did cost me 15 TLEs. 

prateek1985:
20160229 14:23:26
Learned lot of new things but still TLE using segment trees in Java!!! 

lakshay_v06:
20160130 15:45:02
My 100th. :D Done using Mo's Algorithm + Fast I/O and Fast I/O + Idea given on ( http://apps.topcoder.com/forums/;jsessionid=5A69961AF7DF7FBB00FDFE13B80B5D2E?module=Thread&threadID=627423&start=0&mc=13 ) <= use BIT instead of segment trees and use printf... Happy Coding... :D Last edit: 20160131 13:14:47 

vibhorg97:
20160128 15:41:58
using int instead of long long get my q AC 

Anurag Rai:
20160127 19:07:43
(Mo's Algorithm + scanf/printf + dont use function calls, instead use inline) gets accepted ! 
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 