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
killshot667: 2020-12-27 21:28:39

good to question to learn mo's algorithm. Can probably also be solved using Segment trees

mr_cchef: 2020-12-18 15:12:15

Guys, please help me. I am doing this using mo's Algorithm but somehow I get WA.
<snip>

[NG]: Use forum for code review / discussion.

Last edit: 2020-12-18 22:29:18
trungnt2910: 2020-11-23 13:15:19

Persistent Segment Tree Online queries easy AC in one go.
Don't need to use Mo's Algorithm or any other difficult stuff.

sowmiksarker: 2020-11-21 14:23:44

Solved it with:
1. BIT
2. Mo's algo

ankush08: 2020-11-12 06:34:24

I dont know what is Mo's Algo ! Any approach using segment trees ? or will i have to first learn what this algorithm is ?

kapil16garg: 2020-11-08 12:59:10

Those are getting TLE after using Mo's algo...use vector for store frequency instead of map

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.


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