B4568 [山东省小学组体验营 2026] 中位数

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。 你可以将这个序列 **任意打乱重排**，得到一个新的序列 $b_1,b_2,\ldots,b_n$。 定义新序列 $c_i=b_i-i$（其中 $i$ 从 $1$ 开始编号）。 我们定义序列 $c$ 的 **中位数** 为：将 $c$ 从小到大排序后，位于第 $\left\lfloor\dfrac{n+1}{2}\right\rfloor$（下取整）个位置的元素。 请你求出，在序列 $a$ 所有可能的排列方案中，对应序列 $c$ 的中位数的最大值。

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

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

### 【样例 $1$ 说明】 $a=[3,4,7,9,1]$ 重排后得到 $b=[4,7,9,1,3]$，则 $c=[3,5,6,-3,-2]$，排序后中位数是 $3$。 ### 【数据范围】 对于所有的数据，$1\le n\le 10^5$，$|a_i|\le 10^9$。 | 测试点编号 | $n$ | 特殊性质 | |:-:|:-:|:-:| | $1\sim 4$ | $1\le n\le 10$ | 无 | | $5\sim 7$ | $1\le n\le 10^5$ | $a_i=i$ | | $8\sim 12$ | $1\le n\le 10^5$ | $a_i$ 互不相同 | | $13\sim 20$ | $1\le n\le 10^5$ | 无 |