题目描述

定义一个数组的极差为：数组的元素最大值减去最小值。
小红拿到了一个数组，她准备进行恰好一次操作：选择一个非空区间，将其中所有元素都乘以 $2$。
小红希望最小化数组的极差，你能帮帮她吗？

输入描述

第一行输入一个正整数 $n \left(1 \leq n \leq 10^5\right)$ 代表数组中的元素数量。
第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$$\left(1 \leq a_i \leq 10^9\right)$ 代表数组元素。

输出描述

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

样例1

输入

2
3 4

输出

2

说明

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