题目描述

给你一个由 $n$ 个整数构成的数组，你可以从中选择一个任意区间 $[l, n]$中任取两个数$x_1, x_2$，然后从 $[1,l) \cup (r,n]$ 中任取两个数 $y_1,y_2$，使得 $|x_1-y_1|+|x_2-y_2|$ 的值最大，输出 $|x_1-y_1|+|x_2-y_2|$ 的最大值。

输入格式

第一行输入一个整数 $n(4 \le n \le 10^8)$，第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n(1 \le a_1, a_2, \dots, a_n < 10^9)$，每个整数之间由空格隔开。

输出格式

一行，输出最大值。

样例

5
9 6 5 12 3

13