← 返回题目列表

AtCoder · awc0025_d

D. 星座观测之旅

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥正在天文台引导星座观测之旅。

在天文台的观景台上, N 望远镜沿着数轴安装。每个望远镜的编号为 1 to N和望远镜 i 安装在坐标处 X_i。没有两个望远镜安装在同一坐标处。

游览期间,参与者在望远镜前出发 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
  • 第一行包含一个整数 N 代表望远镜数量,整数 S 代表起始望远镜的编号,一个整数 Q 代表移动次数,以空格分隔。
  • 第二行包含整数 X_1, X_2, \ldots, X_N 代表每个望远镜的坐标,以空格分隔。
  • X_i 代表望远镜的坐标 i.

输出

在一行上打印参与者所在望远镜的编号 Q 移动。


样本输入 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