1827 . Yet another simple task ^____^
TopCoder
Tags
Description
given a sequence $B = B_0, B_1, \dots , B_{N-1}$
for each query $(P, K)$, find the minimum $S$
$s.t.$ there are at least $K$ entries in $B$ that satisfies
- $\left| P - i \right| \leq S$
- $B_i \leq S$
where $B_i$ denotes the $i^{th}$ entry of $B$
Input Format
The first line contains two integers $N, M$.
The second line contains $N$ integers separated with spaces. This is the sequence $B$.
The following $M$ lines are $M$ queries and each query is consists of two integers $P, K$.
Output Format
For each query, you should output one integer denoting your answer.
Sample Input 1
10 2
1 2 3 2 10 2 3 3 3 2
1 3
3 3
1 2 3 2 10 2 3 3 3 2
1 3
3 3
Sample Output 1
2
2
2
Hints
$1 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$1 \leq B_i \leq N$
$0 \leq P < N$
$1 \leq K \leq N$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |