DQUERY - D-query


Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, ..., aj.

Input

  • Line 1: n (1 ≤ n ≤ 30000).
  • Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).
  • Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
  • In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

Output

  • For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, ..., aj 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
Kishore: 2018-02-13 07:45:41

did anyone do it in java? I did it using MO along with fast I/o but getting TLE

jatin_tayal: 2018-01-14 18:46:46

don't use pair while using MO , use a structure instead !

karthik1997: 2017-12-29 12:37:02

Cant Believe it . With Fast I/O ,my results are :
Offline BIT 0.06s , Offline Segment Tree 0.15s and MO's algorithm 0.09s .
Hence Segment tree is slowest :P .

chandan kumar: 2017-12-15 08:59:47

Offline BIT with fast I/O - 0.10s

Last edit: 2017-12-15 09:03:36
pratham_1: 2017-12-15 08:28:34

BIT - 0.17s , MO-0.30s , AC ;)

chandan kumar: 2017-12-15 06:25:15

offline fenwick tree/segment tree

suraj_: 2017-12-13 07:18:28

thanks!! @tanavya
MO jai ho

Last edit: 2017-12-13 10:47:23
chachaji_harsh: 2017-12-09 12:53:56

can somebody pls tell why my code is printing unexpectedly wrong output (only sometimes)while my mo's implementation looks all good
https://ideone.com/hMdw6I

tanavya: 2017-12-01 13:08:35

Use ceil(sqrt(Q)) instead of int(sqrt(Q)) to get it to pass!!

gaurav__404: 2017-10-31 20:59:31

AC in one go ;). Use Mo's Algo(see https://www.hackerearth.com/practice/notes/mos-algorithm/) and scanf / printf instead of cin / cout.


Added by:Duc
Date:2008-10-26
Time limit:0.227s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:© VNOI