题目描述

给定一个长度为 $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$。

输出格式

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

5
3 4 7 9 1

3

6
2 6 10 14 20 30

9

5
1 5 5 5 10

3

提示

【样例 $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$。