weyryafjnm;
erfvjuaweikm

92.3% (48/52)

36.5% (133/364)

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$.

Sample Input

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

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

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