M. [L3-1] 视频剪辑

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

你拍摄了一段长度为 帧的延时视频。第 帧的清晰度评分为 。由于存储与发布限制,你可以对视频进行若干次剪辑操作:

  • 每次操作必须选择当前视频中的一个连续恰好 的片段并将其删除;
  • 删除后,剩余片段会自动拼接成一个新视频;
  • 你可以进行任意次操作(也可以一次都不做),但最终剩余视频必须至少包含 1 帧。

平台用剩余视频所有帧清晰度评分的上中位数作为“整体清晰度”。
对长度为 的序列,将其升序排序后,上中位数定义为第 个元素(即当 为偶数时取偏大的那个中间值)。

请你计算:通过若干次剪辑后,剩余视频的“整体清晰度”(上中位数)最大能达到多少。

输入格式

第一行两个整数

第二行 个整数

输出格式

输出一个整数,表示可获得的最大“整体清晰度”(上中位数)。

样例

样例输入 1
6 2
1 9 4 8 12 6
样例输出 1
12
样例输入 2
7 3
29 11 1 1 1 21 18
样例输出 2
29

数据范围与提示