{"problem":{"name":"Choose","description":{"content":"给定一个长度为 $n$ 的序列 $a$。 你需要选出 $a$ 的 $k$ 个长度均为 $L$ $(1\\le L\\le n-k+1)$ 的不同**连续**子序列  $C(a,l_1,l_1+L-1),C(a,l_2,l_2+L-1),\\dots,C(a,l_k,l_k+L-1)$，其中 $1\\le l_1<l_2< \\dots< l_k\\le n-L+1$。 记这 $k$ 个子序列中极差的最小值","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10059"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的序列 $a$。\n\n你需要选出 $a$ 的 $k$ 个长度均为 $L$ $(1\\le L\\le n-k+1)$ 的不同**连续**子序列 \n$C(a,l_1,l_1+L-1),C(a,l_2,l_2+L-1),\\dots,C(a,l_k,l_k+L-1)$，其中 $1\\le l_1<l_2< \\dots< l_k\\le n-L+1$。\n\n记这 $k$ 个子序列中极差的最小值为 $X$，你需要求出 $X$ 的最大值。同时，你还需要求出，在满足 $X$ 最大的情况下  $L$ 的最小值。\n\n## Input\n\n**本题有多组测试数据。**\n\n第一行一个整数 $T$，表示测试数据组数。\n\n对于每组测试数据：\n\n- 第一行两个整数 $n,k$。\n- 第二行 $n$ 个整数 $a_1,a_2,...,a_n$。\n\n## Output\n\n对于每组测试数据：\n\n- 一行两个整数 $X,L$，表示所求极差和子序列长度。\n\n[samples]\n\n## Background\n\n[加强版](https://www.luogu.com.cn/problem/U397746)\n\n对于一个长度为 $n$ 的序列 $a$ ，定义 $a$ 的极差表示 $a$ 中最大值与最小值之差；定义 $C(a,l,r)$ 表示 $a$ 的**连续**子序列 $[a_l,a_{l+1},\\dots,a_r]$，其中 $1\\le l\\le r\\le n$。\n\n## Note\n\n**【样例 1 解释】**\n\n- $k=1$ 时，极差最大不超过 $4$，此时满足长度最短的一种方案为 $[1,2,3,4,5]$。\n- $k=2$ 时，极差最大不超过 $3$，此时满足长度最短的一种方案为 $[1,2,3,4],[2,3,4,5]$。\n- $k=3$ 时，极差最大不超过 $2$，此时满足长度最短的一种方案为 $[1,2,3],[2,3,4],[3,4,5]$。\n\n**【数据规模与约定】**\n\n**本题采用捆绑测试。**\n\n| 子任务 | 分值 | $n\\le$ | $k\\le$ | 特殊性质 |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1$ | $5$ | $10^5$ | $n$ | $a_i$ 均相等 |\n| $2$ | $5$ | $10^5$ | $1$ | 数据随机生成 |\n| $3$ | $10$ | $100$ | $n$ | 所求的 $X$ 不超过 $10^3$ |\n| $4$ | $20$ | $100$ | $n$ | 无 |\n| $5$ | $20$ | $10^4$ | $n$ | 无 |\n| $6$ | $40$ | $10^5$ | $n$ | 无 |\n\n对于 $100\\%$ 的数据，$1\\le T\\le 10$，$1\\le n\\le 10^5$，$1\\le k\\le n$，$-10^9\\le a_i\\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10059","tags":["贪心","二分","单调队列","洛谷原创","O2优化","前缀和","ST 表","洛谷月赛"],"sample_group":[["3\n5 1\n1 2 3 4 5\n5 2\n1 2 3 4 5\n5 3\n1 2 3 4 5","4 5\n3 4\n2 3"],["2\n5 1\n1 2 2 2 3\n5 2\n1 2 2 2 3","2 5\n1 2"]],"created_at":"2026-03-03 11:09:25"}}