分数: 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