题目描述

给定一个长度为 $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\dfrac{n+1}{2}\right\rfloor$ 个位置的元素。

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

$\lfloor x \rfloor$ 表示向下取整符号，即不超过 $x$ 的最大整数。

输入格式

第一行包含一个正整数 $n$ —— 表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 表示给定的初始序列。

输出格式

输出一行，一个整数，表示在所有可能的排列方案中，序列 $c$ 中位数的最大值。

样例输入 1

5
3 4 7 9 1

样例输出 1

3

样例输入 2

6
2 6 10 14 20 30

样例输出 2

9

样例输入 3

5
1 5 5 5 10

样例输出 3

3

说明

样例解释

在第一个样例中，初始序列为 $a=[3, 4, 7, 9, 1]$。一种能够使中位数达到最大的重排方案是得到 $b=[4, 7, 9, 1, 3]$。 此时对应的序列 $c$ 计算如下：

• $c_1 = 4 - 1 = 3$
• $c_2 = 7 - 2 = 5$
• $c_3 = 9 - 3 = 6$
• $c_4 = 1 - 4 = -3$
• $c_5 = 3 - 5 = -2$

序列 $c = [3, 5, 6, -3, -2]$。将其从小到大排序后为 $[-3, -2, 3, 5, 6]$，长度为 $5$，位于第 $\lfloor\frac{5+1}{2}\rfloor = 3$ 个位置的元素（中位数）是 $3$。

数据范围

对于所有的数据，保证 $1 \le n \le 10^5$，$|a_i| \le 10^9$。 保证所有的输入数值均为整数。

各测试点的附加限制如下表所示：