DQUERY  Dquery
Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274490/problem/O
https://codeforces.com/group/FLVn1Sc504/contest/274490/problem/O
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
soumalya_1:
20201021 16:33:49
use fenwick/bit tree 

tpriyanshu:
20200915 00:13:40
MO's Algorithm, implementation. Do read MO's Algo first. 

thelegend27101:
20200723 09:22:42
MO's ALgo in python gives TLE 

wahidmshafin:
20200703 09:32:27
Offline solution is easier. 

coolboy7:
20200702 13:04:34
they combined mo with segment tree 

amar_shukla1:
20200627 20:05:30
I did using Mos algorithm,how did people did it in 0.01 s.Please tell me if someone has the idea 

bimal15:
20200624 06:16:39
My solution is using Mo's algorithm in java bit it shows TLE why? 

jrseinc:
20200602 13:09:14
Simple BIT problem 

karlo_2107:
20200531 17:14:23
It's a bit


flashadarsh:
20200523 16:49:14
Easy using MO's Algorithm 
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 