分数: 300 分
问题陈述
高桥正在举办一场问答比赛,其中 N 学生参与。
每个学生都会分配一个学生 ID 号 1 to N和学生 i 的测验技能等级为 A_i.
比赛开始时,所有 N 学生留下来,并根据以下规则重复“轮次”:
- 将当前剩余的学生按照学号从小到大的顺序排列,分为 K 从前面。也就是说,第 1 个通过 K第 1 组中排列顺序的学生, (K{+}1)-th 通过 2K第 2 组表格,依此类推。如果最后一组的数量少于 K 学生,它仍然是一个具有该数量学生的单一群体。
- 对于每个组,只有 1 该组中技能水平最高的学生幸存。如果有多位技能等级最高的学生,则其中学号最小的学生生存。 1 学生,那个学生照样生存。)
- 如果只有 1 学生仍然存在,该学生被宣布为冠军,比赛结束。如果 2 或更多学生留下,只保留幸存的学生,我们返回步骤 1 进行下一轮。
每轮至少有 2 剩余的学生,并且自从 K \geq 2,至少一组包含 2 或更多学生,因此每轮剩余学生的数量都会严格减少。因此,比赛在有限轮数后结束。
确定最终赢得比赛的学生的学生 ID 号。
约束
- 2 \leq N \leq 5 \times 10^5
- 2 \leq K \leq N
- 1 \leq A_i \leq 10^9
- 所有输入值均为整数。
输入
N K A_1 A_2 \ldots A_N
- 第一行包含整数 N 代表学生人数和整数 K 代表每组的最大学生人数,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个学生的技能水平,以空格分隔。
输出
在一行上打印获胜学生的学生 ID 号。
示例输入 1
6 2 3 1 4 1 5 9
示例输出 1
6
示例输入 2
10 3 5 2 8 3 7 1 6 4 9 10
示例输出 2
10
示例输入 3
15 4 12 5 9 3 15 7 11 2 8 14 1 6 13 10 4
示例输出 3
5