#LUOGUP7927. [PA2021] Koszulki

[PA2021] Koszulki

题目描述

nn 个人参加一场比赛,其中第 ii 个人的得分为 aia_i

主办方决定至少颁发 kk 件礼物。

但是,若 1x,yn,axay\exist 1 \leq x, y \leq n, a_x \geq a_yxx 未拿到礼物但 yy 拿到礼物,xx 会不满意。

主办方希望每个人都满意,求颁发的礼物数量的最小值。

输入格式

第一行,两个整数 n,kn, k

第二行,nn 个整数 a1,a2,,ana_1, a_2, \cdots, a_n

输出格式

一行,一个整数,表示所求的值。

5 3
75 90 120 75 40
4

提示

样例 #1 解释

最优方案为除了最后一人以外全部送礼物。

数据范围

对于 100%100\% 的数据,1kn2×1031 \leq k \leq n \leq 2 \times 10^31ai1201 \leq a_i \leq 120