题目描述

すぬけ君有一个长度为 $N$ 的整数序列 $A$。

すぬけ君可以在 $A$ 中任意选择 $3$ 个位置进行切分，将其分成 $4$ 个（非空的）连续子序列 $B,C,D,E$。切分的位置可以自由选择。

现在，设这四个子序列 $B,C,D,E$ 的元素和分别为 $P,Q,R,S$。すぬけ君希望 $P,Q,R,S$ 的最大值与最小值之差的绝对值越小越好。请你求出 $P,Q,R,S$ 的最大值与最小值之差的绝对值可能取得的最小值。

输入格式

输入以如下格式从标准输入给出。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出 $P,Q,R,S$ 的最大值与最小值之差的绝对值可能取得的最小值。

样例 1

输入

5
3 2 4 1 2

输出

2

样例 2

输入

10
10 71 84 33 6 47 23 25 52 64

输出

36

样例 3

输入

7
1 2 3 1000000000 4 5 6

输出

999999994

说明/提示

限制条件

• $4 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 输入均为整数。

样例解释 1

如果将 $A$ 分割为 $B,C,D,E=(3),(2),(4),(1,2)$，则 $P=3,Q=2,R=4,S=1+2=3$。此时，$P,Q,R,S$ 的最大值为 $4$，最小值为 $2$，它们的差的绝对值为 $2$。无法使最大值与最小值之差的绝对值小于 $2$，因此答案为 $2$。

由 ChatGPT 4.1 翻译