竞争名额

题目描述

$R$ 电竞俱乐部的年度首发阵容选拔已进入最终决胜阶段，队内 $n$ 名潜力选手已按照试训加入的先后顺序确定了各自的编号 $1\sim n$。每位选手的初始竞技评分为 $a[i]$，其中 Ming 是第 $k$ 号选手，正全力冲击新赛季的首发席位。

作为俱乐部的主教练，你在最终决胜阶段的选拔机制中设置了 $m$ 轮 1v1 环节，每轮 1v1 你可以指定两名选手 $i,j$ 进行 solo 对决，对决后两人的竞技评分将会调整：

• 若 $a[i]\neq a[j]$，一般情况下两者中评分较低者会输掉比赛，竞技评分减少 $1$，而评分较高者的评分则保持不变
• 若 $a[i]= a[j]$，一般情况下两者不相上下，双方的竞技评分均保持不变

同一名选手可以被你指定多次参与 1v1 环节，也可全程不被指定参与；任意两名选手也允许重复对决。全部 1v1 结束后，教练组将按照最终竞技评分从高到低公布排名，若两名选手评分相同，则试训加入更早（编号更小）的选手排名更靠前，最终排名将直接决定首发人选。

你很青睐第 $k$ 号选手 Ming，因此你想制定一个最优的 1v1 顺序，使得 Ming 选手最终能获得尽可能靠前的排名。请你给出最优情况下 Ming 的最高排名。

输入格式

第一行三个正整数 $n, m, k$，分别代表选手总数、1v1轮次、Ming 选手的编号

第二行 $n$ 个正整数 $a[1\sim n]$，代表每名选手的初始竞技评分

输出格式

一行一个整数表示答案

输入输出样例

输入 #1

6 2 2
5 5 5 6 3 2

输出 #1

2

输入 #2

6 3 3
7 5 5 8 6 5

输出 #2

3

样例解释

对于样例 $1$，Ming 的初始竞技评分为 $a[2]=5$，一种最优方案如下：

• 第一轮：安排 $i=1, j=4$ 两名选手对决，由于 $a[1]=5,a[4]=6$，所以对决后 $a[1]=4, a[4]=6$
• 第二轮：安排 $i=1, j=6$ 两名选手对决，由于 $a[1]=4,a[6]=2$，所以对决后 $a[6]=1, a[1]=4$

最终所有选手的竞技评分为 $[4, 5, 5, 6, 3, 1]$，Ming 的竞技评分 $a[2] = 5$ 排第二

数据范围

对于 $40\%$ 的数据，$2 \leq n \leq 100$，$1 \leq a[i] \leq 1000$

对于所有数据，保证 $2 \leq n \leq 500000$，$1 \leq a[i] \leq 10000$，$1 \leq k, m \leq n$