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 


Được gửi lên bởi:Jimmy
Ngày:2008-10-26
Thời gian chạy:1s-1.5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Minesweeper

hide comments
2021-05-27 18:00:30
Tham khảo: https://vnspoj.github.io/problems/DQUERY
2020-11-23 13:20:44
Persistent Segment Tree xử lý Online 1 đấm AC ko biết Mo là gì.
Đjt mẹ wibu.

Last edit: 2020-11-23 13:21:24
2020-06-27 13:39:51
Tham khảo:
Solution: http://megaurl.in/cWKj
Code: http://megaurl.in/zpzoD
2020-02-12 10:40:40
Bài này dùng Mo Algo cài cơ bản để xử lý offline. Mấy thánh cho mình tham khảo cách online :V
2019-09-21 16:51:23
So amazing Yoshikage Kira ^^
love the way that you take care of yourself
2019-08-16 07:15:07
My name is Yoshikage Kira. I'm 33 years old. My house is in the northeast section of Morioh, where all the villas are, and I am not married. I work as an employee for the Kame Yu department stores, and I get home every day by 8 PM at the latest. I don't smoke, but I occasionally drink. I'm in bed by 11 PM, and make sure I get eight hours of sleep, no matter what. After having a glass of warm milk and doing about twenty minutes of stretches before going to bed, I usually have no problems sleeping until morning. Just like a baby, I wake up without any fatigue or stress in the morning. I was told there were no issues at my last check-up. I'm trying to explain that I'm a person who wishes to live a very quiet life. I take care not to trouble myself with any enemies, like winning and losing, that would cause me to lose sleep at night. That is how I deal with society, and I know that is what brings me happiness. Although, if I were to fight I wouldn't lose to anyone.
2019-08-15 15:39:44
Bài này dùng Mo Algorithm là AC. cin/scanf ko quan trọng
2019-08-10 16:28:12
các bạn nhớ lưu ý chỉ số nhé <3
2019-07-24 11:04:06
ư ư dễ vl
2019-07-24 10:12:16
tuấn việt buscu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.