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
zhouyexuan:
20230727 12:41:32
莫队和树没有关系吧（雾 

tiachi:
20230315 06:07:16
just use president Tree to solve this 

ultimate_von:
20230314 15:47:38
Me too! AC with MO algorithm


masterbaiter:
20221203 21:27:43
Solved in one go using your mom 

sebastiamestre:
20220725 17:36:04
AC in one go with sorting + range sum 

iskhakkutbilim:
20220725 12:14:01
Solved using MO's in one go


goku20001:
20220629 09:08:44
If you want to solve using segment tree (online) then lookup merge sort tree first. 

cjn2007:
20211102 08:25:51
Binary Indexed Tree with off line algorithms.


darksun:
20211101 10:33:18
Can anyone tell me the solution using Binary indexed trees ? 

sicho_mohit:
20210728 08:23:18
If you want to solve this using segment tree.

Added by:  Jimmy 
Date:  20081026 
Time limit:  1s1.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Minesweeper 