{"problem":{"name":"B. Maximum of Maximums of Minimums","description":{"content":"You are given an array _a_1, _a_2, ..., _a__n_ consisting of _n_ integers, and an integer _k_. You have to split the array into exactly _k_ non-empty subsegments. You'll then compute the minimum integ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF870B"},"statements":[{"statement_type":"Markdown","content":"You are given an array _a_1, _a_2, ..., _a__n_ consisting of _n_ integers, and an integer _k_. You have to split the array into exactly _k_ non-empty subsegments. You'll then compute the minimum integer on each subsegment, and take the maximum integer over the _k_ obtained minimums. What is the maximum possible integer you can get?\n\nDefinitions of subsegment and array splitting are given in notes.\n\n## Input\n\nThe first line contains two integers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤  105) — the size of the array _a_ and the number of subsegments you have to split the array to.\n\nThe second line contains _n_ integers _a_1,  _a_2,  ...,  _a__n_ ( - 109  ≤  _a__i_ ≤  109).\n\n## Output\n\nPrint single integer — the maximum possible integer you can get if you split the array into _k_ non-empty subsegments and take maximum of minimums on the subsegments.\n\n[samples]\n\n## Note\n\nA subsegment \\[_l_,  _r_\\] (_l_ ≤ _r_) of array _a_ is the sequence _a__l_,  _a__l_ + 1,  ...,  _a__r_.\n\nSplitting of array _a_ of _n_ elements into _k_ subsegments \\[_l_1, _r_1\\], \\[_l_2, _r_2\\], ..., \\[_l__k_, _r__k_\\] (_l_1 = 1, _r__k_ = _n_, _l__i_ = _r__i_ - 1 + 1 for all _i_ > 1) is _k_ sequences (_a__l_1, ..., _a__r_1), ..., (_a__l__k_, ..., _a__r__k_).\n\nIn the first example you should split the array into subsegments \\[1, 4\\] and \\[5, 5\\] that results in sequences (1, 2, 3, 4) and (5). The minimums are _min_(1, 2, 3, 4) = 1 and _min_(5) = 5. The resulting maximum is _max_(1, 5) = 5. It is obvious that you can't reach greater result.\n\nIn the second example the only option you have is to split the array into one subsegment \\[1, 5\\], that results in one sequence ( - 4,  - 5,  - 3,  - 2,  - 1). The only minimum is _min_( - 4,  - 5,  - 3,  - 2,  - 1) =  - 5. The resulting maximum is  - 5.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"给你一个包含 $n$ 个整数的数组 $[a_1, a_2, ..., a_n]$ 和一个整数 $k$。你需要将数组恰好划分为 $k$ 个非空子段。然后，对每个子段计算其最小值，并在得到的 $k$ 个最小值中取最大值。你能得到的最大可能整数是多少？\\n\\n子段和数组划分的定义见注释。\\n\\n第一行包含两个整数 $n$ 和 $k$ ($1 ≤ k ≤ n ≤  10^5$) —— 数组 $a$ 的大小以及你需要将数组划分成的子段数量。\\n\\n第二行包含 $n$ 个整数 $a_1,  a_2,  ...,  a_n$ ($ - 10^9  ≤  a_i ≤  10^9$)。\\n\\n请输出一个整数 —— 如果你将数组划分为 $k$ 个非空子段，并在每个子段的最小值中取最大值，你能得到的最大可能整数。\\n\\n数组 $a$ 的子段 $[l,  r]$ ($l ≤ r$) 是序列 $a_l,  a_{l + 1},  ...,  a_r$。\\n\\n将包含 $n$ 个元素的数组 $a$ 划分为 $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}), ..., (a_{l_k}, ..., a_{r_k})$。\\n\\n在第一个例子中，你应该将数组划分为子段 $[1, 4]$ 和 $[5, 5]$，得到序列 $(1, 2, 3, 4)$ 和 $(5)$。最小值分别为 $\\min(1, 2, 3, 4) = 1$ 和 $\\min(5) = 5$。最终的最大值为 $\\max(1, 5) = 5$。显然，你无法获得更大的结果。\\n\\n在第二个例子中，你唯一的选择是将数组划分为一个子段 $[1, 5]$，得到序列 $( - 4,  - 5,  - 3,  - 2,  - 1)$。唯一的最小值是 $\\min( - 4,  - 5,  - 3,  - 2,  - 1) =  - 5$。最终的最大值是 $ - 5$。\"},{\"iden\":\"input\",\"content\":\"第一行包含两个整数 $n$ 和 $k$ ($1 ≤ k ≤ n ≤  10^5$) —— 数组 $a$ 的大小以及你需要将数组划分成的子段数量。第二行包含 $n$ 个整数 $a_1,  a_2,  ...,  a_n$ ($ - 10^9  ≤  a_i ≤  10^9$)。\"},{\"iden\":\"output\",\"content\":\"请输出一个整数 —— 如果你将数组划分为 $k$ 个非空子段，并在每个子段的最小值中取最大值，你能得到的最大可能整数。\"},{\"iden\":\"examples\",\"content\":\"输入\\n5 2\\n1 2 3 4 5\\n输出\\n5\\n\\n输入\\n5 1\\n-4 -5 -3 -2 -1\\n输出\\n-5\"},{\"iden\":\"note\",\"content\":\"数组 $a$ 的子段 $[l,  r]$ ($l ≤ r$) 是序列 $a_l,  a_{l + 1},  ...,  a_r$。\\n\\n将包含 $n$ 个元素的数组 $a$ 划分为 $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}), ..., (a_{l_k}, ..., a_{r_k})$。\\n\\n在第一个例子中，你应该将数组划分为子段 $[1, 4]$ 和 $[5, 5]$，得到序列 $(1, 2, 3, 4)$ 和 $(5)$。最小值分别为 $\\min(1, 2, 3, 4) = 1$ 和 $\\min(5) = 5$。最终的最大值为 $\\max(1, 5) = 5$。显然，你无法获得更大的结果。\\n\\n在第二个例子中，你唯一的选择是将数组划分为一个子段 $[1, 5]$，得到序列 $( - 4,  - 5,  - 3,  - 2,  - 1)$。唯一的最小值是 $\\min( - 4,  - 5,  - 3,  - 2,  - 1) =  - 5$。最终的最大值是 $ - 5$。\"}]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 10^5 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in [-10^9, 10^9] $ for all $ i \\in \\{1, \\dots, n\\} $.\n\nA **splitting** of $ A $ into $ k $ non-empty subsegments is a sequence of indices $ 1 = l_1 \\leq r_1 < l_2 \\leq r_2 < \\dots < l_k \\leq r_k = n $ such that for all $ i \\in \\{2, \\dots, k\\} $, $ l_i = r_{i-1} + 1 $, and each subsegment is $ S_i = (a_{l_i}, a_{l_i+1}, \\dots, a_{r_i}) $.\n\nFor each subsegment $ S_i $, define $ m_i = \\min(S_i) $.  \nDefine $ M = \\max\\{m_1, m_2, \\dots, m_k\\} $.\n\n**Objective**  \nMaximize $ M $ over all possible splittings of $ A $ into exactly $ k $ non-empty contiguous subsegments.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF870B","tags":["greedy"],"sample_group":[["5 2\n1 2 3 4 5","5"],["5 1\n-4 -5 -3 -2 -1","\\-5"]],"created_at":"2026-03-03 11:00:39"}}