题目描述

visit_world 最近在研究 Game theory, 他设计了一个游戏，邀请他的好朋友 A 和 B 来玩。

游戏在一个长为 $N$ 的整数序列 $\left\{a_{i}\right\}$ 上进行， $A$ 和 $B$ 轮流操作, 由 $A$ 先手。每次操作是指选择序列最左 / 最右边的 元素，并删掉它。

游戏一直进行，直到剩下一个元素 $x$, 我们定义这次游戏的输出为 $x$ 。 A 想让输出尽可能大，B 想让它尽可能小。

但是，就在他们开始玩游戏之前, B 突然接到了一个女朋友的电话，此时 A 就有时间对序列动手脚了。具体来说， A 可以在游戏开始之前先执行恰好 $K$ 次操作, 得到一个对自己更有利的局面（当然, 游戏开始之后仍然是 A 先 手)。

现在，问 A 和 B 都按照最优策略玩游戏，游戏的输出值会是多少。

特别地，如果输入的 $K=-1$, 这表示你需要对 $K=0 \sim N-1$ 都计算答案。

输入格式

第一行两个整数 $N, K$, 意义如题目描述.

第二行 $N$ 个非负整数, 描述序列 $\left\{a_{i}\right\}_{\circ} 0 \leq a_{i} \leq 10^{9}$.

输出格式

若 $K \geq 0$, 输出一行一个整数，表示答案。

若 $K=-1$, 输出一行 $N$ 个整数, 第 $i$ 个数表示 $K$ 取 $i-1$ 时的答案。

样例

5 1
1 2 4 5 3

5

5 2
1 2 4 5 3

4

样例解释1

$\mathrm{A}$ 在游戏开始之前删掉 1, 并在第一轮中删掉 2 . 此时，无论 B 删 3 或者 $4, A$ 就删掉另一个并保留 5 .

样例解释2

游戏的最后一次操作不是由 $\mathrm{A}$ 执行， 故输出无法取到最大值 5 .

大数据

限制范围

对 $100 \%$ 的数据, $2 \leq N \leq 2 \times 10^{5},-1 \leq K \leq N-1 .$

• 子任务 1 (15 分 $)$ : 保证 $N \leq 300$.
• 子任务 2 (20 分) : 保证 $N \leq 2000$.
• 子任务 3 (10 分) : 保证 $K=0$.
• 子任务 4 (20 分) : 保证 $K \geq 0$.
• 子任务 5 (35 分) : 无特殊限制 .