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

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

Added by:Duc
Date:2008-10-26
Time limit:1s-1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:© VNOI