DQUERY - D-query


Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274490/problem/O

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
soumalya_1: 2020-10-21 16:33:49

use fenwick/bit tree

tpriyanshu: 2020-09-15 00:13:40

MO's Algorithm, implementation. Do read MO's Algo first.

thelegend27101: 2020-07-23 09:22:42

MO's ALgo in python gives TLE

wahidmshafin: 2020-07-03 09:32:27

Offline solution is easier.

coolboy7: 2020-07-02 13:04:34

they combined mo with segment tree

amar_shukla1: 2020-06-27 20:05:30

I did using Mos algorithm,how did people did it in 0.01 s.Please tell me if someone has the idea

bimal15: 2020-06-24 06:16:39

My solution is using Mo's algorithm in java bit it shows TLE why?

jrseinc: 2020-06-02 13:09:14

Simple BIT problem

karlo_2107: 2020-05-31 17:14:23

It's a bit

flashadarsh: 2020-05-23 16:49:14

Easy using MO's Algorithm


Added by:Jimmy
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:Minesweeper