CF1341B Nastya and Door

2 月 14 日，Denis 决定送给 Nastya 一个情人节礼物，他想不出更好的主意，于是在门上画了一个巨大的红心，长度为 $k$（$k \ge 3$）。Nastya 对这个礼物感到非常困惑，于是她决定把门拆了，把它扔到山上。 山脉由一个从左到右的高度序列 $a_1, a_2, \dots, a_n$ 描述（$k \le n$）。保证相邻的高度不相等（即对于所有 $1 \leq i \leq n-1$，都有 $a_i \ne a_{i+1}$）。 对于区间 $[l, r]$（从 $l$ 到 $r$），山峰定义为所有满足 $l < i < r$，且 $a_{i-1} < a_i$ 且 $a_i > a_{i+1}$ 的下标 $i$。需要注意的是，区间的边界 $l$ 和 $r$ 不是山峰。例如，如果 $n=8$ 且 $a=[3,1,4,1,5,9,2,6]$，那么区间 $[1,8]$ 上只有两个山峰（下标为 $3$ 和 $6$），而区间 $[3,6]$ 上没有山峰。 为了拆门，Nastya 会把门扔到长度为 $k$ 的连续山脉区间 $[l, l+k-1]$ 上（$1 \le l \le n-k+1$）。当门碰到山峰时会断成两部分，这些部分会继续分别下落并在碰到山峰时继续断开，如此反复。形式化地说，门最终会被分成 $p+1$ 部分，其中 $p$ 是区间 $[l, l+k-1]$ 上的山峰数量。 Nastya 想让门尽可能多地碎成碎片。请帮她选择一个山脉区间 $[l, l+k-1]$，使得该区间内的山峰数量最大。如果有多个最优区间，Nastya 希望选择左端点 $l$ 最小的那个。 形式化地说，你需要选择一个区间 $[l, l+k-1]$，使得其中的山峰数量最大。在所有这样的区间中，输出左端点 $l$ 最小的那个。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$3 \leq k \leq n \leq 2 \cdot 10^5$），分别表示山的数量和门的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 10^9$，$a_i \neq a_{i+1}$），表示山的高度。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出两个整数 $t$ 和 $l$，分别表示门最多可以被分成的部分数，以及对应的长度为 $k$ 的区间的左端点。

在第一个样例中，应选择从 $2$ 到 $7$ 的山脉区间。在该区间内，下标 $3$ 和 $6$ 是山峰，因此答案为 $3$（只有 $2$ 个山峰，所以门会被分成 $3$ 部分）。不难发现，区间 $[1, 6]$ 和 $[3, 8]$ 都不合适，因为它们分别只有 $1$ 个山峰（对于第一个区间，下标 $6$ 不是山峰，对于第二个区间，下标 $3$ 不是山峰）。 在第二个样例中，应选择从 $2$ 到 $4$ 的山脉区间。在该区间内，下标 $3$ 是山峰，因此答案为 $2$（只有 $1$ 个山峰，所以门会被分成 $2$ 部分）。 在第三个样例中，应选择从 $1$ 到 $4$ 的山脉区间。在该区间内，下标 $3$ 是山峰，因此答案为 $2$（只有 $1$ 个山峰，所以门会被分成 $2$ 部分）。可以看到，在区间 $[2, 5]$、$[4, 7]$ 和 $[5, 8]$ 上，山峰数量也是 $1$，但这些区间的左端点都大于 $[1, 4]$，所以它们不是正确答案。 由 ChatGPT 4.1 翻译