All submissions for this problem are available.
There are a lot of hills on the surface of Mars, and you have information about the heights of N of those hills located one after the other. Your supervisor is now interested in finding the number of distinct heights of hills in arbitrary ranges. Your task is to answer his queries.
The first line contains an integer N, the number of hills. The next line contains N integers, denoting the heights of the hills. The hills are numbered from 1 to N and the ith integer ai denotes the height of the ith hill.
The next line contains an integer Q, the number of queries to answer. The next Q lines contain two integers each, xi and ri, where ri denotes the ending location of the range of hills for the ith query.
Let Qi be the answer to the ith query, then the value of li+1, the starting location of the range of hills for the next query, is obtained by adding xi+1 to Qi.
Q0 = 0
li = xi + Qi-1 (for i >= 1)
Output Q integers, where the ith integer denotes the answer of the ith query, i.e. number of distinct heights among the hills in range [li, ri].
- 1 ≤ N ≤ 106
- 1 ≤ Q ≤ 106
- 1 ≤ ai ≤ 109
- 1 ≤ li ≤ ri ≤ N
- -(N-1) ≤ xi ≤ N-1
Input: 10 1 3 2 1 3 1 3 2 1 3 10 8 9 2 7 4 8 1 6 1 7 -1 10 0 8 -2 10 1 7 -1 7 Output: 2 2 3 2 3 3 3 3 2 3
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions