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

harisagar: 2016-12-28 09:57:28

use faster io(not cin,cout).............

Last edit: 2016-12-28 09:58:05
rihaz_zahir: 2016-12-28 09:21:22

std::ios_base::sync_with_stdio(false);
use above code in main for fast I/O in c++,
this will run cin/cout faster than scanf/printf.
google search for details.

hamjosh1: 2016-12-27 21:41:18

fast io to use in cpp

vengatesh15: 2016-12-22 17:08:02

my first MO type Problem AC after 3WA

testing java: 2016-12-13 12:58:03

Nice problem, not so nice time limit. Wasted a lot of time on making java solution fast enough.


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