请参见 down.zip 中的题面。

题目描述

小 Y 的朋友小 F 准备了 $n$ 个蛋糕，她把这些蛋糕从小到大排成一排，第 $i$ 个蛋糕的大小为 $a_i$。

为了帮助小 F 控制身材，小 Y 可以吃掉其中的任意个蛋糕，可以不吃，但不能全部吃掉。

假设最后剩下 $m$ 个蛋糕，按照从左到右的顺序，它们的大小依次为 $b_1\le b_2\le \cdots\le b_m$。

小 F 会在剩下的蛋糕中进行两次选择，两次选择之间互不影响。

她第一次会选择剩余蛋糕中从左往右第 $\lceil \frac m2\rceil$ 个蛋糕，即大小为 $b_{\lceil m/2\rceil}$ 的蛋糕。

第二次选择时，对于 $1\le i\le m$，令 $c_i$ 表示剩余蛋糕中大小与 $b_i$ 相同的蛋糕数量，然后选择 $c_i$ 最大的一个蛋糕，如果有多个 $c_i$ 最大的蛋糕，则选择最左边的，即大小最小的一个。

现在小 Y 希望小 F 两次选择的蛋糕的大小之差的绝对值尽可能大。

注意，小 F 两次选择可能选中同一个蛋糕，此时大小之差为 $0$。

你需要帮小 Y 求出，在她所有合法的吃蛋糕方式中，小 F 两次选中的蛋糕大小之差的绝对值最大是多少。

输入格式

从文件 cake.in 中读入数据。

第一行一个整数 $n$，表示蛋糕的数量。

第二行 $n$ 个整数，第 $i$（$1\le i\le n$）个为 $a_i$，表示从左到右第 $i$ 个蛋糕的大小，保证对于所有 $1\le i\le n-1$ 均有 $a_i\le a_{i+1}$。

输出格式

输出到文件 cake.out 中。

输出一行一个整数，表示小 F 选择的两个蛋糕大小之差的绝对值的最大值。

样例 1 输入

4
1 5 6 8

样例 1 输出

5

样例 1 解释

吃掉大小为 $5$ 的蛋糕，小 F 会选择大小为 $6$ 和 $1$ 的两个蛋糕。

样例 2

见选手目录下的 cake/cake2.in 与 cake/cake2.ans。

该样例满足子任务 $1$ 的约束条件。

样例 3

见选手目录下的 cake/cake3.in 与 cake/cake3.ans。

该样例满足子任务 $2$ 的约束条件。

样例 4

见选手目录下的 cake/cake4.in 与 cake/cake4.ans。

该样例满足子任务 $3$ 的约束条件。

样例 5

见选手目录下的 cake/cake5.in 与 cake/cake5.ans。

该样例满足子任务 $4$ 的约束条件。

样例 6

见选手目录下的 cake/cake6.in 与 cake/cake6.ans。

该样例满足子任务 $5$ 的约束条件。

数据范围

对于所有测试数据，保证 $1\le n\le 10^5$，$1\le a_i\le 10^9$，对于所有 $1\le i\le n-1$ 均有 $a_i\le a_{i+1}$。

特殊性质 A：$a_1,a_2,\dots,a_n$ 中至多有三种不同的值。

特殊性质 B：$a_1,a_2,\dots,a_n$ 两两不同。

本题开启所有合理的子任务依赖。