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
psiphon_exe: 2017-03-23 11:56:47

Made with simple logic without any algorithm

gkcs: 2017-03-16 05:37:12

Hi All!
I picked this problem up for explaining Mo's algorithm at work. Here is a video tutorial on the same:
https://youtu.be/hqaRYgsLpUI
Cheers!

evenpeng_91: 2017-03-12 08:55:58

Does anyone get AC using Golang?

ruben_ash: 2017-03-10 19:07:53

MOooOOO0000ooo0O0O0

Last edit: 2017-03-10 19:14:49
nilabja16180: 2017-03-07 20:24:35

MO's Algo with fast IO, 0.25 sec!
First Mo's algorithm!

cake_is_a_lie: 2017-02-21 02:35:45

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
NEVER use std::endl (use '\n')
MOs
AC in 0.19

starbot: 2017-02-19 18:15:38

MO+CIN/COUT+IOS_BASE>>TLE
MO+SCANF/PRINTF>>>AC
feeling happy

akshay31057: 2017-02-03 23:51:33

Learnt something new.....M0 Rocks!!

SHASHANK GUPTA: 2017-01-08 12:14:00

If getting TLE even after [MO+fast I/O] , use struct (instead of pair) and even after this also you get TLE , look your comparator function.

adityaghosh96: 2017-01-03 04:50:00

O(n*sqrt(n)) with scanf,printf.


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