D - K-th Nearest Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 425 点

問題文

数直線上に N+Q 個の点 A_1,\dots,A_N,B_1,\dots,B_Q があり、点 A_i の座標は a_i、点 B_j の座標は b_j です。

j=1,2,\dots,Q それぞれについて、以下の問題に答えてください。

  • 点 A_1,A_2,\dots,A_N のうち点 B_j との距離が k_j 番目に近い点を X としたとき、点 X と点 B_j との距離を求めよ。 より厳密には、点 A_i と点 B_j との距離を d_i として、(d_1,d_2,\dots,d_N) を昇順に並び替えてできる列を (d_1',d_2',\dots,d_N') としたとき、d_{k_j}' を求めよ。

制約

  • 1\leq N,Q \leq 10^5
  • -10^8\leq a_i,b_j \leq 10^8
  • 1\leq k_j\leq N
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
a_1 a_2 \dots a_N
b_1 k_1
b_2 k_2
\vdots
b_Q k_Q

出力

Q 行出力せよ。 l\ (1\leq l \leq Q) 行目には、j=l としたときの問題に対する答えを整数として出力せよ。

入力例 1

4 3
-3 -1 5 6
-2 3
2 1
10 4

出力例 1

7
3
13

1 番目のクエリについて説明します。

点 A_1,A_2,A_3,A_4 と点 B_1 との距離は順に 1,1,7,8 なので、点 B_1 との距離が 3 番目に近いのは点 A_3 です。 よって、点 A_3 と点 B_1 との距離である 7 を出力します。

入力例 2

2 2
0 0
0 1
0 2

出力例 2

0
0

同じ座標に複数の点がある可能性もあります。

入力例 3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

出力例 3

11
66
59
54
88

Score : 425 points

Problem Statement

There are N+Q points A_1,\dots,A_N,B_1,\dots,B_Q on a number line, where point A_i has a coordinate a_i and point B_j has a coordinate b_j.

For each j=1,2,\dots,Q, answer the following question:

  • Let X be the point among A_1,A_2,\dots,A_N that is the k_j-th closest to point B_j. Find the distance between points X and B_j. More formally, let d_i be the distance between points A_i and B_j. Sort (d_1,d_2,\dots,d_N) in ascending order to get the sequence (d_1',d_2',\dots,d_N'). Find d_{k_j}'.

Constraints

  • 1 \leq N, Q \leq 10^5
  • -10^8 \leq a_i, b_j \leq 10^8
  • 1 \leq k_j \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
a_1 a_2 \dots a_N
b_1 k_1
b_2 k_2
\vdots
b_Q k_Q

Output

Print Q lines. The l-th line (1 \leq l \leq Q) should contain the answer to the question for j=l as an integer.

Sample Input 1

4 3
-3 -1 5 6
-2 3
2 1
10 4

Sample Output 1

7
3
13

Let us explain the first query.

The distances from points A_1, A_2, A_3, A_4 to point B_1 are 1, 1, 7, 8, respectively, so the 3rd closest to point B_1 is point A_3. Therefore, print the distance between point A_3 and point B_1, which is 7.

Sample Input 2

2 2
0 0
0 1
0 2

Sample Output 2

0
0

There may be multiple points with the same coordinates.

Sample Input 3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

Sample Output 3

11
66
59
54
88