思路:简单动态规划:前缀最值

一个显然的思路是枚举染色的断点，然后分别计算前缀和后缀的极差，相减取绝对值。这些答案里取最小即可。

由于n 比较大，我们需要提前算出前缀每个位置的极差，以及后缀每个位置的极差。

f1[i] 表示前i 个位置的极差，f2[i] 表示后i 个位置的极差。

f1[i] = max(max[i-1], a[i]) - min(min[i-1], a[i])

注意这里的max[i-1]和max[i-1]可以用一个变量维护，不需要开辟数组去存储。

题目内容

小红有一个长度为$n$的数组，他想要选择一个下标$i(1≤i<n)$，随后，将$a_i$及其左边元素全部染红，$a_i$右边的元素全部染蓝，使得红色元素的极差和蓝色元素的极差†的差的绝对值最小，请你直接输出这个值。

†:极差 是指数组中最大值和最小值的差。

输入描述

第一行输入一个整数$n(2≤n≤10^5)$代表数组的长度。

第二行$n$个整数$a_1,a_2,...,a_n(1≤a_i≤10^9)$代表数组的元素。

输出描述

在一行上输出一个正整数，表示红色元素的极差和蓝色元素的极差的差的绝对值的最小值。

样例1

输入

5
1 2 4 3 5

输出

1

说明

红色元素为$1,2,4$，极差为$4-1=3$;蓝色元素为$3,5$，极差为$5-3=2$，差的绝对值为$1$。