题目描述

龙 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 部分。

9 3
1 2 3 3 4 3 1 5 2

7 2 5

5 2
2 2 1 2 2

4 0 1

2 1
6 7

14 1 1

提示

提示

$\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		该队伍的强度不是可能的最大值。
7 0 2	50%	队伍强度正确，尽管输出的队伍不正确。
7 2 4		若要获得满分，队伍大小必须尽可能大。

$\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$	--