/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君はチェスの勝ち抜き大会を主催することになりました。この大会には N 人の選手が参加し、それぞれ 1 から N までの番号が付けられています。各選手 i にはレーティング S_i が定められており、すべての選手のレーティングは異なります。
大会では、最後に 1 人の選手が残るまで試合を繰り返します。各試合では、その時点でまだ脱落していない選手の中から 2 人を選んで 1 対 1 で戦わせます。試合ではレーティングが大きい方の選手が必ず勝利し、負けた選手は大会から脱落します。したがって、大会全体で合計 N - 1 回の試合が行われます。
どの試合でどの 2 人を戦わせるかは、主催者である高橋君が自由に決めることができます。高橋君はすべての選手のレーティングを事前に知っており、試合の勝敗は完全に予測できるため、大会開始前にすべての対戦の組み合わせを最適に計画できます。
高橋君には応援している選手がいます。それは選手 K です。高橋君は対戦の組み合わせを最適に決めることで、選手 K が勝利する試合の回数をできるだけ大きくしたいと考えています。選手 K は、自分よりレーティングが大きい選手と対戦すると負けて脱落し、それ以降は勝利数が増えることはありません。
選手 K が最大で何回勝利できるかを求めてください。
制約
- 2 \leq N \leq 10^5
- 1 \leq K \leq N
- 1 \leq S_i \leq 10^9
- S_i はすべて異なる
- 入力はすべて整数
入力
N K S_1 S_2 \ldots S_N
- 1 行目には、選手の人数を表す N と、応援する選手の番号を表す K が、スペース区切りで与えられる。
- 2 行目には、各選手のレーティングを表す S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
出力
選手 K が最大で勝利できる試合数を 1 行で出力せよ。
入力例 1
4 3 5 1 3 2
出力例 1
2
入力例 2
5 2 3 10 7 1 5
出力例 2
4
入力例 3
10 5 20 50 10 5 30 80 15 25 40 60
出力例 3
5
Score : 300 pts
Problem Statement
Takahashi is going to organize a chess elimination tournament. N players participate in this tournament, each numbered from 1 to N. Each player i has a rating S_i, and all players have distinct ratings.
In the tournament, matches are repeated until only 1 player remains. In each match, 2 players who have not yet been eliminated are chosen to compete against each other in a one-on-one match. The player with the higher rating always wins, and the losing player is eliminated from the tournament. Therefore, a total of N - 1 matches are held throughout the tournament.
Takahashi, as the organizer, is free to decide which 2 players compete in each match. Since Takahashi knows all players' ratings in advance and can perfectly predict the outcome of every match, he can optimally plan all match pairings before the tournament begins.
Takahashi has a player he is rooting for: player K. Takahashi wants to optimally arrange the match pairings to maximize the number of matches that player K wins. Player K will lose and be eliminated if matched against a player with a higher rating, after which their win count can no longer increase.
Determine the maximum number of matches player K can win.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq K \leq N
- 1 \leq S_i \leq 10^9
- All S_i are distinct
- All inputs are integers
Input
N K S_1 S_2 \ldots S_N
- The first line contains N, the number of players, and K, the number of the player Takahashi is rooting for, separated by a space.
- The second line contains the ratings S_1, S_2, \ldots, S_N of each player, separated by spaces.
Output
Output in one line the maximum number of matches player K can win.
Sample Input 1
4 3 5 1 3 2
Sample Output 1
2
Sample Input 2
5 2 3 10 7 1 5
Sample Output 2
4
Sample Input 3
10 5 20 50 10 5 30 80 15 25 40 60
Sample Output 3
5