M-低谷(hard)_中国地质大学（武汉）2024年新生赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

这是本题的困难版本。在这个版本中， $n$ 的数据范围更大。同时，本题困难版本仅在同步赛中出现，以替代校内赛的交互题。

有一个长度为 $n$ 的数组，现在可以对其进行 $k$ 次操作，每次操作过程如下：

现定义低谷：

对于数组 $a$ ，若对于下标 $i(2\le i\le n-1)$ ，使得 $a_i < a_{i-1}$ 且 $a_i < a_{i+1}$ ，则称 $i$ 为数组 $a$ 的一个低谷。

lzt想知道 $k$ 次操作后，该数组的低谷最多有多少个。

共两行。第一行包含两个整数，分别表示数组长度和操作次数。

第二行包含个整数，表示数组。

输出一行一个整数，表示数组的低谷最大个数。

示例1

复制

7 3
2 2 3 4 6 2 3

复制

将数组中第二个数减1，第四个数减2，就能得到三个低谷。