/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は、N 人の生徒が参加するクイズ大会の司会を担当しています。
各生徒には 1 から N までの出席番号が付けられており、生徒 i のクイズの実力値は A_i です。
大会の開始時点では N 人全員が残っており、以下のルールに従って「ラウンド」を繰り返します。
- 現在残っている生徒を出席番号の小さい順に並べ、その順序で先頭から K 人ずつのグループに分ける。すなわち、並べた列の 1 番目から K 番目までを第 1 グループ、K{+}1 番目から 2K 番目までを第 2 グループ、…とする。最後のグループの人数が K 人未満になる場合は、そのままの人数で 1 つのグループとする。
- 各グループについて、そのグループ内で実力値が最も高い生徒 1 人だけが勝ち残る。実力値が最も高い生徒が複数いる場合は、その中で出席番号が最も小さい生徒が勝ち残る。（グループの人数が 1 人の場合は、その生徒がそのまま勝ち残る。）
- 勝ち残った生徒が 1 人になったら、その生徒を優勝者とし大会を終了する。2 人以上残っている場合は、勝ち残った生徒のみを残して手順 1 に戻り、次のラウンドを行う。
各ラウンドでは残っている生徒が 2 人以上おり、K \geq 2 より少なくとも 1 つのグループには 2 人以上の生徒が含まれるため、ラウンドごとに残っている生徒の人数は必ず減少します。したがって、大会は有限回のラウンドで終了します。
最終的に優勝する生徒の出席番号を求めてください。
制約
- 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
- 1 行目には、生徒の人数を表す整数 N と、各グループの最大人数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各生徒の実力値を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
優勝する生徒の出席番号を 1 行で出力せよ。
入力例 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
Score : 300 pts
Problem Statement
Takahashi is hosting a quiz tournament in which N students participate.
Each student is assigned a student ID number from 1 to N, and student i has a quiz skill level of A_i.
At the start of the tournament, all N students remain, and "rounds" are repeated according to the following rules:
- Arrange the currently remaining students in ascending order of their student ID numbers, and divide them into groups of K from the front. That is, the 1st through K-th students in the arranged sequence form group 1, the (K{+}1)-th through 2K-th form group 2, and so on. If the last group has fewer than K students, it remains as a single group with that number of students.
- For each group, only the 1 student with the highest skill level in that group survives. If there are multiple students with the highest skill level, the one with the smallest student ID number among them survives. (If a group has only 1 student, that student survives as is.)
- If only 1 student remains, that student is declared the champion and the tournament ends. If 2 or more students remain, only the surviving students are kept and we return to step 1 to conduct the next round.
In each round, there are at least 2 remaining students, and since K \geq 2, at least one group contains 2 or more students, so the number of remaining students strictly decreases with each round. Therefore, the tournament ends after a finite number of rounds.
Determine the student ID number of the student who ultimately wins the tournament.
Constraints
- 2 \leq N \leq 5 \times 10^5
- 2 \leq K \leq N
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains the integer N representing the number of students and the integer K representing the maximum number of students per group, separated by a space.
- The second line contains the integers A_1, A_2, \ldots, A_N representing each student's skill level, separated by spaces.
Output
Print the student ID number of the winning student on a single line.
Sample Input 1
6 2 3 1 4 1 5 9
Sample Output 1
6
Sample Input 2
10 3 5 2 8 3 7 1 6 4 9 10
Sample Output 2
10
Sample Input 3
15 4 12 5 9 3 15 7 11 2 8 14 1 6 13 10 4
Sample Output 3
5