说明

小乔开了一家蛋糕店。每天他都会做 n 块蛋糕，并把它们排成一排放在柜台里。每块蛋糕由于用料和制作工艺的不同，都会有自己的美味度。

小乔每卖一块蛋糕的时候只会从这一排的头和尾取出蛋糕。例如他卖出第一块蛋糕时，就只会从 1 号和 n 号蛋糕中选一个卖。

现在小斯来到了蛋糕店。他是当天的第一位顾客，想一次性买走 k 块蛋糕。他是老顾客了，所以小乔希望小斯买走的所有蛋糕中的美味度最大值尽可能大。

输入格式

第一行为两个整数 n,k；第二行为 n 个整数，依次是每块蛋糕的美味值。

输出格式

小斯买走的蛋糕中的美味度最大值的最大值。

样例

5 3
1 3 3 5 3

5

提示

1 <= k <= n <= 100000。

所有蛋糕的美味值都为正且不会大于 1000000。