该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

中位数

题目描述

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

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

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

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

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

输入格式

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

输出格式

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

样例

5
3 4 7 9 1

3

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

6
2 6 10 14 20 30

9

5
1 5 5 5 10

3

数据范围

$1\le n \le 10^5$，$|a_i| \le 10^9$