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
mahir111: 2017-06-26 18:35:40

use scanf printf with sqrt decomposition...even fast i/o fails with cin,cout...gave me several tle

anilkumar1998: 2017-06-21 19:49:46

If using MO Algorithm,be clear at sizes of different arrays. 1<= n <= 30000 , 1<= ai <= 10^6 ,1<= q <=2*10^5

praney_rai: 2017-06-20 05:56:51

ac after 5 wa :3

sandeepg97: 2017-06-15 23:36:04

Use scanf and printf with ios_base::sync_with_stdio(0);cin.tie(0) if using SQRT Decomposition

siddharth_0196: 2017-06-10 06:35:41

cin/cout works fine with fast I/O! BIT!

yash_18: 2017-06-08 12:06:19

cin/cout fails even with fast i/o,use scanf/printf instead..

leafbebop: 2017-06-01 17:50:17

@evenpeng_91 Yes.
fmt is slow. DO NOT use it.
I have written a fastio (for integers only, for now) here: https://bitbucket.org/snippets/leafbebop/pnxqM

mkfeuhrer: 2017-05-28 22:21:18

fast i/o needed!! use scanf / printf - MO's :-)

cj23897: 2017-05-21 06:49:53

Be aware people.
The limit of n is less than 3*10^5 not 30000

deepak_k1414: 2017-04-29 13:13:04

anyone solved it using segment tree


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