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
elmer_fudd: 2018-05-10 20:39:15

i try to solve using direct sqrt decomposition but RTE

my code : ***************see notes below**************

it is possible or not?

Last edit: 2018-05-10 22:58:27
mrvincy: 2018-05-04 03:08:23

max(n) is 3e5 and not 3e4

coderslegacy: 2018-04-23 00:44:12

Ac in one go use Mo's Algorithm

akshatjain02: 2018-04-14 23:22:18

Solved it using both Mo's Algorithm and Offline Segment Tree :')

ac_traits: 2018-04-11 10:58:55

I set maxN = (int)3e4 + 10 and get AC

gangchil: 2018-03-29 12:08:47

mo with cin/cout gives tle use printf/scanf instead (.31s)and value of n is probably <= 300010 costed me lots of wa ;)

Last edit: 2018-03-31 01:29:59
da_201501443: 2018-03-06 14:20:28

Can anybody share your code ??
My code has got 0.59s which contain solution using offline BIT.

da_201501443: 2018-03-06 14:00:32

@mmshn1380
Decrease the value of maxn to 30010 and you will get AC.

mmshn1380: 2018-03-03 18:06:44

why my code get TLE :/
https://ideone.com/mzMuBH

humiko_1: 2018-02-21 20:19:12

n is smaller or equal to 3*10^5, not 3*10^4. Please fix that.


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