TopCoder

Thumb   5
Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

92.3% (36/39)

Submission's AC Ratio

36.1% (107/296)

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

10 2
1 2 3 2 10 2 3 3 3 2
1 3
3 3

Sample Output

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 (KiB) Output Limit (KiB) Subtasks
0 2000 131072 262144 1
1 2000 131072 262144 2
2 2000 131072 262144 3
3 2000 131072 262144 4
4 2000 131072 262144 5
5 2000 131072 262144 6