DQUERY - D-query


{assign var="code" value="DQUERY"} {if $par==""} {assign var=par value=$locale} {/if}

{if $par=="vn"} {literal}

Truy vấn-d

Cho một dãy số n phần tử a1, a2, ..., an và một số các truy vấn-d. Một truy vấn-d là một cặp (i, j) (1 ≤ i ≤ j ≤ n). Với mỗi truy vấn-d (i, j), bạn cần trả về số phần tử phân biệt nằm trong dãy con ai, ai+1, ..., aj.

Dữ liệu

  • Dòng 1: n (1 ≤ n ≤ 30000).
  • Dòng 2: n số a1, a2, ..., an (1 ≤ ai ≤ 106).
  • Dòng 3: q (1 ≤ q ≤ 200000), số lượng truy vấn- d.
  • Trong q dòng sau, mỗi dòng chứa 2 số i, j biểu thị một truy vấn-d (1 ≤ i ≤ j ≤ n).

Kết quả

  • Với mỗi truy vấn-d (i, j), in ra số phần tử phân biệt thuộc dãy con ai, ai+1, ..., aj trên một dòng.

     

Ví dụ

Dữ liệu
5
1 1 2 1 3
3
1 5
2 4
3 5

Kết quả
3
2
3 

{/literal}{elseif ($par=="en" || $par=="")}{literal}

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 

{/literal} {/if}


hide comments
viniet_sw: 2019-03-27 14:30:38

dimaag ka bhosada kar dia question ne

vartik_s: 2019-03-20 12:09:07

very strict time limit. got tle even after using cin.tie and sync with stdio. Finally got accepted using scanf and printf. Used MO's algorithm. Watch GKCS' video on the topic and you are good to go

Last edit: 2019-03-20 12:09:44
itssanat: 2019-03-09 11:16:03

better to use scanf and printf because of strict time

manojmanu: 2019-03-09 09:10:52

MO's in java get TLE ...........WTF

caro_linda2018: 2019-02-19 02:26:01

Very strict time

Last edit: 2019-02-19 02:26:18
kkkrr: 2019-01-04 01:07:31

No need of fast I/O......
Only MO's with printf,scanf works......

Last edit: 2019-01-04 01:08:10
ttnhuy313: 2019-01-01 11:02:15

cheated but AC anyway
But however, I AC with the constraint n <= 3e5 so I believe that the original constraint is correct!

Last edit: 2019-01-01 11:03:37
mulx10: 2018-12-27 11:18:53

/MO gives AC W/o fast I/O

Last edit: 2018-12-27 11:19:20
nidhi_061: 2018-12-25 22:24:08

as kevin said It's limit is now 3000001.

kevin: 2018-11-22 10:38:32

The problem statement is wrong. Please fix it.
If I set the range of n to 30001, it gives me wrong answer, but it gives me correct answer if I set the range of n to 300001, it's accepted.

[---------see notes below---------https://id--ne.com/**********--------]
Try this code with editing maxn to 30001 and 300001

Last edit: 2018-11-22 13:37:58

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