DQUERY  Dquery
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
killshot667:
20201227 21:28:39
good to question to learn mo's algorithm. Can probably also be solved using Segment trees 

mr_cchef:
20201218 15:12:15
Guys, please help me. I am doing this using mo's Algorithm but somehow I get WA.


trungnt2910:
20201123 13:15:19
Persistent Segment Tree Online queries easy AC in one go.


sowmiksarker:
20201121 14:23:44
Solved it with:


ankush08:
20201112 06:34:24
I dont know what is Mo's Algo ! Any approach using segment trees ? or will i have to first learn what this algorithm is ? 

kapil16garg:
20201108 12:59:10
Those are getting TLE after using Mo's algo...use vector for store frequency instead of map 

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. 
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 