题意化简

对于每个位置$i(1 \leq i \leq n)$ , 对应求出

然后答案就是

本题为2024年9月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$。