ZZULIOJ

题目描述

定义一个序列的权值和为这个序列中元素的总和。现在给你一个序列 a ，请从中选出一个子数组 b ，使得该子数组权值和最大。

但这个求解问题太简单了，我们决定添加两个条件：

1：定义奖励数组为：你选出的子数组中，应该有至少 k 个连续的数对 x, y，满足 x >= y 。形式上说，在你选出的子数组 b 中，应该有至少 k 个下标 i ，满足 b_i >= b_i+1(1 <= i < |b|)。

2：定义惩罚值为：你选出的子数组的长度。

给你一个长度为 n 的序列 a ，请从中选出一个子数组 b，在满足其为奖励数组的前提下，最小化惩罚值（你不需要最大化子数组权值和）。

注：子数组是指在原序列开头或结尾删除一段连续数组，得到剩余的连续数组。

输入

第一行输入一个正整数 n(1<= n <= 2e5)，代表给定序列的长度。
第二行输入一个正整数 k(1 <= k <= 2e5)，代表满足奖励数组条件下的最小数对个数。
第三行输入 n 个正整数 a_i(-2e5 <= a_i <= 2e5)，代表给定序列中的元素。

输出

输出一行一个整数，代表**在满足其为奖励数组的前提下，最小的惩罚值。如果没有一个子数组满足这样的条件，输出-1。

样例输入 Copy

9
3
7 -3 1 2 -9 1 2 -3 5

样例输出 Copy

提示

5
5
10 9 8 7 6

-1

样例1中，选择了 {7,-3,1,2,-9,1,2,-3}。其中有 3 对数对满足 b_i >= b_i+1 。
样例2中，没有一个子数组能满足条件，输出-1。

来源/分类