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
mulx10:
20181227 11:18:53
/MO gives AC W/o fast I/O


nidhi_061:
20181225 22:24:08
as kevin said It's limit is now 3000001. 

kevin:
20181122 10:38:32
The problem statement is wrong. Please fix it.


arvindj97:
20181109 09:36:07
Getting tle while using java with fenwick tree


davitmarg:
20181107 14:47:01
AC in 14 mo 

alexandro5432:
20181026 20:43:37
offline BIT+very fast io+inline functions+many optimisations=AC


skirim06:
20180929 00:27:56
MO's + fast io + cpp = AC


dipankar12:
20180923 12:13:32
java+mo getting TLE. Anyone solved using JAVA and mo? Last edit: 20180923 12:13:50 

redcenturion:
20180918 08:17:59
Can we solve this by segment tree ? 

lax_99:
20180831 08:26:07
If you're using MO's algorithm, make sure you use array instead of vector and array of frequencies instead of Hash Table. 
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 