D - 星座観測ツアー 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は天文台で星座観測ツアーのガイドをしています。

天文台の観測デッキには N 個の望遠鏡が数直線上に設置されています。各望遠鏡には 1 から N までの番号が付けられており、望遠鏡 i は座標 X_i の位置に設置されています。どの 2 つの望遠鏡も異なる座標に設置されています。

ツアーでは、参加者は最初に望遠鏡 S の前にいます。その後、以下のルールに従って移動を Q 回繰り返します。

  • 現在いる望遠鏡を除いた N-1 個の望遠鏡のうち、現在の位置からの距離（座標の差の絶対値）が最も小さい望遠鏡へ移動する。距離が最も小さい望遠鏡が複数存在する場合は、そのうち番号が最も小さい望遠鏡へ移動する。

なお、直前にいた望遠鏡へ戻ることは禁止されていません（現在いる望遠鏡自身のみが移動先の候補から除外されます）。

Q 回の移動後に参加者がいる望遠鏡の番号を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq S \leq N
  • 1 \leq Q \leq 10^{18}
  • -10^9 \leq X_i \leq 10^9
  • X_i \neq X_j （i \neq j）
  • 入力はすべて整数

入力

N S Q
X_1 X_2 \cdots X_N
  • 1 行目には、望遠鏡の数を表す整数 N 、最初にいる望遠鏡の番号を表す整数 S 、移動回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各望遠鏡の座標を表す整数 X_1, X_2, \ldots, X_N が、スペース区切りで与えられる。
  • X_i は望遠鏡 i の座標を表す。

出力

Q 回の移動後に参加者がいる望遠鏡の番号を 1 行で出力せよ。

入力例 1

3 1 3
1 3 6

出力例 1

2

入力例 2

4 2 4
0 10 5 20

出力例 2

1

入力例 3

5 3 1000000000
1 4 6 9 15

出力例 3

3

入力例 4

10 5 1000000000000000000
-1000000000 -500000000 -100 0 50 100 200 500000000 999999999 1000000000

出力例 4

5

入力例 5

2 1 1000000000000000000
0 1

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is guiding a constellation observation tour at an observatory.

On the observation deck of the observatory, N telescopes are installed along a number line. Each telescope is numbered from 1 to N, and telescope i is installed at coordinate X_i. No two telescopes are installed at the same coordinate.

During the tour, participants start in front of telescope S. After that, they repeat the following movement Q times:

  • Among the N-1 telescopes excluding the one you are currently at, move to the telescope whose distance (absolute difference of coordinates) from your current position is the smallest. If there are multiple telescopes with the smallest distance, move to the one with the smallest number among them.

Note that returning to the telescope you were at immediately before is not prohibited (only the telescope you are currently at is excluded from the movement candidates).

Determine the number of the telescope where the participant is after Q moves.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq S \leq N
  • 1 \leq Q \leq 10^{18}
  • -10^9 \leq X_i \leq 10^9
  • X_i \neq X_j (i \neq j)
  • All inputs are integers

Input

N S Q
X_1 X_2 \cdots X_N
  • The first line contains an integer N representing the number of telescopes, an integer S representing the number of the starting telescope, and an integer Q representing the number of moves, separated by spaces.
  • The second line contains integers X_1, X_2, \ldots, X_N representing the coordinates of each telescope, separated by spaces.
  • X_i represents the coordinate of telescope i.

Output

Print on one line the number of the telescope where the participant is after Q moves.

Sample Input 1

3 1 3
1 3 6

Sample Output 1

2

Sample Input 2

4 2 4
0 10 5 20

Sample Output 2

1

Sample Input 3

5 3 1000000000
1 4 6 9 15

Sample Output 3

3

Sample Input 4

10 5 1000000000000000000
-1000000000 -500000000 -100 0 50 100 200 500000000 999999999 1000000000

Sample Output 4

5

Sample Input 5

2 1 1000000000000000000
0 1

Sample Output 5

1