Problem Description

中位数（median）

【题目描述】

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$。

你可以将这个序列任意打乱重排，得到一个新的序列 $b_1, b_2, \ldots, b_n$。

定义新序列 $c_i = b_i - i$（其中 $i$ 从 1 开始编号）。

我们定义序列 $c$ 的中位数为：将 $c$ 从小到大排序后，位于第 $\lfloor \frac{n+1}{2} \rfloor$（下取整）个位置的元素。

请你求出，在序列 $a$ 所有可能的排列方案中，对应序列 $c$ 的中位数的最大值。

【输入格式】

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$。

【输出格式】

一行一个整数，表示答案。

【样例1输入】

5
3 4 7 9 1

【样例1输出】

3

【样例1说明】

$a=[3,4,7,9,1]$ 重排后得到 $b=[4,7,9,1,3]$，则 $c=[3,5,6,-3,-2]$，排序后中位数是 3。

【样例2输入】

6
2 6 10 14 20 30

【样例2输出】

11

【样例3输入】

5
1 5 5 5 10

【样例3输出】

3

【数据范围】

对于所有的数据，$1 \le n \le 10^5$，$|a_i| \le 10^9$。

5
3 4 7 9 1

3

Source

2026年山东省信息学体验营