1827 . Yet another simple task ^____^

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

93.3% (56/60)

Submission's AC Ratio

38.8% (150/387)

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

Sample Output 1

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 131072 262144 1
1 2500 131072 262144 2
2 2500 131072 262144 3
3 2500 131072 262144 4
4 2500 131072 262144 5
5 2500 131072 262144 6
Submit
Back to Top