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

Advitiya: 2016-08-06 13:55:06

BIT-0.27s
MO's-0.43s
Nice problem :)

askerov5555: 2016-08-04 22:22:21

I got AC with 0.4 second. With O(qlog(q) + qlog(n)) and scanf.

Last edit: 2016-08-04 22:23:18
vineet1003: 2016-07-18 15:05:06

getting tle with cin and cout but ac with scanf and printf..

kiwi1995: 2016-07-16 10:16:01

used MO :)
BIT gave me TLE :/

Deepak : 2016-07-06 17:53:53

learned something new.my first offline processing question.

TP: 2016-06-30 22:29:04

AC(0.30) with Bit + Sorting + (use printf,scanf). cin,cout and vectors cost me 1 TLE. AC (0.50) with MO and scanf.

Last edit: 2016-07-01 01:32:05
ahmad_gafer: 2016-06-08 04:19:20

AC with BIT+sorting , first submission :D

kliu31415: 2016-06-05 06:07:05

Mo's algorithm+slow IO is somehow faster than 2D range tree with fast IO... lol


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