题目描述

给定一个整数数组$array$，代表一系列时间点上的信号强度值。请在这些时间点中找出一个波峰区间 $[i, j]$（其中$i \le j$），满足以下两个连续阶段：

1. 区间前半段是单调非递减（即对于$i \le k < s \le m$，有$array[k] \le array[s]$）
2. 区间后半段是单调非递增（即对于$m \le n < o \le j$，有$array[n] \ge array[o]$）

必须同时出现两个阶段才能构成一个合法的波峰区间！

题目内容

给定一个整数数组 $array$ ，代表在一系列连续时间点上检测到的信号强度值。我们需要在这一系列时间点中找出一个区间 $[i,j]$ (其中 $i<=j$ )，满足以下条件：

1.区间内的信号强度值先呈现单调非递減趋势(即对于 $i<= k<s<= m$，有 $array[k] <= array[s]$)

2.紧接着呈现单调非递增趋势(即对于 $m<=n<o<=j$，有 $array[n]>= aray[o]$)

3.这里的单调非递减和非递增趋势允许存在相等的相邻值。

在满足上述条件的区间叫做“波峰区间"，在所有的“波峰区间“中，找到信号强度最大值与最小值差值最大的那个区间，并返回这个最大差值。

$0<=array.length<=1000$

$array[i] ≥ 0$

输入描述

第一行输入一个数字 $m$ ，代表要输入的数组 $array$ 内的数字数量。

第二行输入 $m$ 个数字，数字用空格隔开。

输出描述

输出最大差值

样例1

输入

8
1 2 3 5 4 4 8 1

输出

7

说明

$[1,2,3,5,4,4]$ 是一个满足条件的区间，最大值是 $5$ ，最小值是 $1$ ，最大差值是 $4$ 。

$[4.8,1]$ 是第二个满足条件的区间，最大值是 $8$，最小值是 $1$ ，最大差值是 $7$ 。两个区间比较，最终最大差值是 $7$

样例2

输入

5
15 15 15 15 15

输出

0

说明

整个数组都满足先单调非递减后单调非递增的条件(因为所有值相等)。信号强度的最大值和最小值都是 $15$ ，差值为 $15-15=0$ 。

样例3

输入

6
3 8 12 10 6 9

输出

9

说明

满足条件的区间为 $[3,8,12,10,6]$ ，在此区间内，$[3,8,12]$ 单调非递减，$[12,10,6]$ 单调非递增。信号强度的最大值为 $12$ ，最小值为 $3$ ，差值为 $12-3=9$ ，这是所有满足条件区间中的最大差值。