/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋先生は、担当するクラスの期末テストの成績処理を行っています。
このクラスには N 人の生徒がおり、それぞれの生徒には 1 から N までの出席番号が重複なく付けられています。期末テストは 0 点以上 100 点以下の整数で採点され、各生徒の得点が確定しました。生徒 i（出席番号 i の生徒）の得点は S_i 点です。
高橋先生は成績上位者を表彰するため、N 人の生徒全員を次のルールに従って一列に並べた成績順位表を作ろうとしています。
- 得点が異なる生徒同士では、得点が高い生徒をより前に並べる。
- 得点が同じ生徒同士では、出席番号が小さい生徒をより前に並べる。
すなわち、得点の降順を第 1 の基準、出席番号の昇順を第 2 の基準として並べます。出席番号はすべて異なるため、この並び順は一意に定まります。
整数 K が与えられるので、上のルールで並べたとき、先頭から K 番目に位置する生徒の出席番号を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 0 \leq S_i \leq 100
- 入力はすべて整数
入力
N K S_1 S_2 \cdots S_N
- 1 行目には、生徒の人数を表す整数 N と、成績順位表の先頭から何番目の生徒を求めたいかを表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各生徒の得点を表す N 個の整数 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
- S_i は出席番号 i の生徒の得点を表す。
出力
上のルールで N 人を一列に並べたとき、先頭から K 番目に位置する生徒の出席番号を 1 行で出力せよ。
入力例 1
5 3 80 95 70 95 85
出力例 1
5
入力例 2
8 4 72 85 85 90 65 85 78 90
出力例 2
3
入力例 3
15 7 45 78 92 100 67 83 92 55 100 71 83 60 92 45 88
出力例 3
6
Score : 300 pts
Problem Statement
Teacher Takahashi is processing the final exam results for his class.
There are N students in this class, and each student is assigned a unique attendance number from 1 to N. The final exam is scored as an integer between 0 and 100 inclusive, and each student's score has been determined. The score of student i (the student with attendance number i) is S_i points.
To recognize top-performing students, Teacher Takahashi wants to create a ranking list by arranging all N students in a single line according to the following rules:
- Among students with different scores, the student with the higher score is placed earlier.
- Among students with the same score, the student with the smaller attendance number is placed earlier.
In other words, the students are sorted with descending order of scores as the primary criterion and ascending order of attendance numbers as the secondary criterion. Since all attendance numbers are distinct, this ordering is uniquely determined.
Given an integer K, find the attendance number of the student who is positioned K-th from the front when the students are arranged according to the rules above.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 0 \leq S_i \leq 100
- All inputs are integers
Input
N K S_1 S_2 \cdots S_N
- The first line contains two space-separated integers: N, the number of students, and K, indicating that we want to find the student at the K-th position from the front of the ranking list.
- The second line contains N space-separated integers S_1, S_2, \ldots, S_N, representing each student's score.
- S_i represents the score of the student with attendance number i.
Output
Print on a single line the attendance number of the student who is positioned K-th from the front when the N students are arranged in a single line according to the rules above.
Sample Input 1
5 3 80 95 70 95 85
Sample Output 1
5
Sample Input 2
8 4 72 85 85 90 65 85 78 90
Sample Output 2
3
Sample Input 3
15 7 45 78 92 100 67 83 92 55 100 71 83 60 92 45 88
Sample Output 3
6