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
rihaz_zahir: 2016-12-05 09:32:01

where can i find my previous submission for this question?

davidgalehouse: 2016-11-15 05:44:54

0.17s with C++, TLE with C# despite very similar benchmarking on my local machine for a 30k/200k test case... I don't get how, given other ACs with much higher times like .5 or .7... Also the source array is malformed, you'll have to trim before splitting or remove empty entries if trying C#.

Last edit: 2016-11-15 05:47:16
oakszyjrnrdy: 2016-10-26 15:59:26

It's very easy to solve this problem using a data structure called 'Zhuxi Tree' in Chinese(sorry~, i don't know how to call it in English, maybe Chair Tree?).
Time: O(n*logn + q*logn).
Space: O(n*logn).

Last edit: 2016-10-26 16:00:56
vicennial: 2016-10-24 19:20:21

How are people solving it with 0.3+ running time when the time limit itself is 0.227 seconds??

shubh809: 2016-10-19 18:56:29

Last edit: 2016-11-10 12:28:48
blackops: 2016-10-14 06:00:22

Persistent seg tree takes 0.28s…………;
it is feaible to make arr range for 0~30010 :)

kk786: 2016-10-07 13:44:14

nice problem!
BIT- 0.18s
MO's- 0.34s
but n may be > 30000

Last edit: 2016-10-07 13:46:26
imwrkhrd: 2016-08-28 01:42:17

Be aware, n is probably bigger than 30000

advanced: 2016-08-19 19:32:00

learnt something new and amazing

sieunhanbom04: 2016-08-07 07:57:09

cin and cout gave me TLE. printf and scanf fix it.


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 NODEJS PERL 6 VB.net
Resource:© VNOI