TopCoder

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

User's AC Ratio

89.3% (25/28)

Submission's AC Ratio

36.3% (77/212)

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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 131072 65536
1 2000 131072 65536
2 2000 131072 65536
3 2000 131072 65536
4 2000 131072 65536
5 2000 131072 65536