题目描述

定义一个数组的极差为：数组的元素最大值减去最小值。

江月诗拿到了一个数组，他准备进行恰好一次操作：选择一个区间，将其中所有元素都乘以 $2$。

江月诗希望最小化数组的极差，你能帮帮他吗？

输入格式

第一行输入一个正整数 $n(1\leq n \leq 10^5)$。

第二行输入 $n$ 个正整数 $a_1, a_2, a_3, \dots , a_n(1\leq a_i \leq 10^9)$ 代表数组元素。

输出格式

输出一个整数，代表操作恰好一次后，数组的最小极差。

输入样例#1

2
3 4

输出样例#1

2

输入样例#2

4
1 2 4 3

输出样例#2

2

说明/提示

在样例 $1$ 中，选择 $[1,1]$ 区间，数组变为 $\{ 6,4 \}$，极差为 $6-4=2$。

在样例 $2$ 中，操作方案不唯一，可以选择 $[1,2]$ 区间或者 $[1,1]$ 区间。