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$

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

For each query, you should output one integer denoting your answer.

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

2

2

2

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

No. | Testdata Range | Score |
---|---|---|

1 | 0 | 10 |

2 | 1 | 10 |

3 | 2 | 10 |

4 | 3 | 10 |

5 | 4 | 10 |

6 | 5 | 10 |

No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|

0 | 2000 | 131072 | 262144 | |

1 | 2000 | 131072 | 262144 | |

2 | 2000 | 131072 | 262144 | |

3 | 2000 | 131072 | 262144 | |

4 | 2000 | 131072 | 262144 | |

5 | 2000 | 131072 | 262144 |