题目描述

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

输出格式

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

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

样例

5 1
1 2 4 5 3

5

A 在游戏开始之前删掉 $1$，并在第一轮中删掉 $2$。

此时，无论 B 删 $3$ 或者 $4$，A 就删掉另一个并保留 $5$。

5 2
1 2 4 5 3

4

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

数据范围

对 $100 \%$ 的数据，$2 \leq N \leq 2 \times 10^{5}$，$-1 \leq K \leq N-1$，$0 \leq a_{i} \leq 10^{9}$。

• 对于 $15$ 分的数据，$N \leq 300$。
• 对于另外 $20$ 分的数据， $N \leq 2000$。
• 对于另外 $10$ 分的数据，保证 $K=0$。
• 对于另外 $20$ 分的数据，保证 $K \geq 0$。
• 对于另外 $35$ 分的数据，无特殊限制。