P16700 [MCO 2026] 队伍选择

龙 Evirir 是一名竞技飞行教练。它训练着 $N$ 名龙运动员，编号为 $0, 1, \ldots, N - 1$。对于每个 $i$，运动员 $i$ 的速度为 $A_i$。 Evirir 需要为即将到来的团体飞行比赛组建一支队伍。由于一些奇怪的规定，这支队伍必须由一个长度至少为 $K$ 的连续区间组成。也就是说，Evirir 必须选择 $l$ 和 $r$（$0 \le l \le r \le N - 1$），满足 $K \le r - l + 1$，并组建一支由运动员 $l, l+1, \ldots, r$ 组成的队伍。 一支队伍的强度定义为队伍中运动员速度的最小值与最大值之和。请帮助 Evirir 找到一支强度最大的队伍。如果有多支队伍的强度都达到最大值，Evirir 更喜欢运动员数量最多的那一支队伍（因为大队伍看起来更令人印象深刻）。

第一行包含两个用空格分隔的整数 $N$ 和 $K$。 第二行包含 $N$ 个用空格分隔的整数 $A_0, A_1, \ldots, A_{N-1}$。

设 $m$ 为队伍可能达到的最大强度，并且某支强度为 $m$ 的队伍由运动员 $l, l+1, \ldots, r$ 组成。输出三个用空格分隔的整数：$m$、$l$ 和 $r$（$0 \le l \le r \le N - 1$，$K \le r - l + 1$）。 如果有多支队伍都具有最大强度，输出其中任意一支运动员数量最多的队伍。 如果你输出了正确的最大强度以及任意一支合法队伍，你仍然可以获得部分分数。也就是说，输出正确的 $m$，并输出任意整数 $l$ 和 $r$，满足 $0 \le l \le r \le N - 1$ 且 $K \le r - l + 1$。特别地，你总是可以输出 $m$、$0$、$K - 1$。有关评分的详细信息，请参见 Scoring 部分。

### 提示 $\underline{样例\ 1}$ 这个样例适用于子任务 2、4、5 和 6。 这里有 $N = 9$ 名运动员，Evirir 必须选择一支至少包含 $K = 3$ 名运动员的队伍。一种最优选择是 $l = 2$、$r = 5$，此时队伍中运动员的速度分别为 $3$、$3$、$4$ 和 $3$。最小速度为 $3$，最大速度为 $4$，因此队伍强度为 $3 + 4 = 7$。所以输出为 $\texttt{7 2 5}$。 下面是一些其他输出及其结果。 | 输出 | 分数 | 解释 | | :---: | :---: | :--- | | `7 7 8` | 0% | 该队伍包含的运动员少于 3 名。 | | `4 0 2` | 0% | 该队伍的强度不是可能的最大值。 | | `7 0 2` | 50% | 队伍强度正确，尽管输出的队伍不正确。 | | `7 2 4` | 50% | 若要获得满分，队伍大小必须尽可能大。 | $\underline{样例\ 2}$ 这个样例适用于子任务 2、3、4、5 和 6。 注意，输出 $\texttt{4 3 4}$ 也会获得满分，因为这支队伍的强度同样达到了可能的最大值 $4$，并且运动员数量的最大值也是 $2$。 $\underline{样例\ 3}$ 这个样例适用于子任务 1、2、4、5 和 6。 如果队伍只包含一名运动员，那么队伍强度就是该运动员速度的两倍，因为队伍中的最小速度和最大速度都来自这名运动员。 ### 评分 对于所有测试用例，输入满足以下限制： - $1 \le K \le N \le 2 \cdot 10^5$ - 对所有 $0 \le i \le N - 1$，都有 $1 \le A_i \le 10^9$ 对于所有子任务，如果你输出了最大强度以及任意一支合法队伍，你可以获得该子任务 50\% 的分数。 | 子任务 | 分值 | 额外限制 | | :---: | :---: | :---: | | $1$ | $8$ | $K = 1$ | | $2$ | $10$ | $N \le 5000$ | | $3$ | $14$ | 对所有 $0 \le i \le N - 1$，都有 $A_i \le 2$ | | $4$ | $26$ | 对所有 $0 \le i \le N - 1$，都有 $A_i \le 20$ | | $5$ | $10$ | 对所有 $0 \le i \le N - 1$，都有 $A_i \le 50$ | | $6$ | $32$ | -- |