CF870B Maximum of Maximums of Minimums

给定一个包含 $n$ 个整数的数组 $a_{1},a_{2},...,a_{n}$，以及一个整数 $k$。你需要将数组恰好划分为 $k$ 个非空子段。然后，你需要计算每个子段的最小值，并从这 $k$ 个最小值中取最大值。请问你能得到的最大可能值是多少？ 有关子段和数组划分的定义请见提示部分。

第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 10^{5}$），分别表示数组 $a$ 的长度和你需要将其划分成的子段数。 第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$-10^{9} \leq a_{i} \leq 10^{9}$）。

输出一个整数，即将数组划分为 $k$ 个非空子段并取其最小值中的最大值时，可能得到的最大整数。

一个子段 $[l,r]$（$l \leq r$）指的是数组 $a$ 的一段连续子序列 $a_{l},a_{l+1},...,a_{r}$。 将数组 $a$（长度为 $n$）划分为 $k$ 个子段 $[l_{1},r_{1}]$，$[l_{2},r_{2}]$，...，$[l_{k},r_{k}]$，要求 $l_{1}=1$，$r_{k}=n$，且对所有 $i>1$ 有 $l_{i}=r_{i-1}+1$，最终得到 $k$ 个序列 $(a_{l_1},...,a_{r_1}),\ldots,(a_{l_k},...,a_{r_k})$。 在第一个样例中，你应将数组划分为子段 $[1,4]$ 和 $[5,5]$，分别得到序列 $(1,2,3,4)$ 和 $(5)$。其最小值分别为 $min(1,2,3,4)=1$ 和 $min(5)=5$，其最大值为 $max(1,5)=5$。显然无法得到更大的结果。 在第二个样例中，你唯一的做法是将整个数组划分为一个子段 $[1,5]$，得到序列 $(-4,-5,-3,-2,-1)$，其最小值为 $min(-4,-5,-3,-2,-1)=-5$，因此最终结果为 $-5$。 由 ChatGPT 5 翻译