Problem G
Svifdrekamaður
As everyone knows, the kiteman Sigurður Jens is famous for gliding between buildings. Despite being very talented he can not increase his height above the ground after the initial jump. Thus he always has to land at a lower height than where he started.
To prevent trouble and possible collisions Reykjavík has established the rule that all buildings between the building where he starts his flight and the building where he lands have to be lower then both of the endpoints. That is to say, Sigurður Jens may only fly from building $i$ to building $j$ if $a_ i > a_ j$ and for all buildings $k$ between $i$ and $j$ we have $a_ k < a_ i$ and $a_ k < a_ j$.
Sigurður Jens wants his show in Reykjavík to be as exciting as possible, but the excitement of a glide is defined as the distance the glide covers. He thus has to find the best two buildings to glide between. Out of all the buildings Sigurður Jens could choose, can you find out what the maximum excitement he can achieve is?
Input
The first line of the input contains one integer $1 \le n \le 10^5$. The next line contains $n$ integers separated by spaces, $a_1, a_2, \dotsc , a_ n$. For each value $a_ i$ it is guaranteed that $1 \le a_ i \le 10^9$.
Output
Print a single integer, the highest level of excitement possible for a single show. If no shows are possible instead print $0$.
Scoring
|
Group |
Points |
Constraints |
|
1 |
20 |
$1 \le n \le 100$, all $a_ i$ are distinct |
|
2 |
25 |
$1 \le n \le 5\, 000$, all $a_ i$ are distinct |
|
3 |
25 |
$1 \le n \le 10^5$, $1 \le a_ i \le 100$ |
|
4 |
30 |
No further constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
1 20 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 8 12 6 18 4 10 18 7 8 16 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 9 1 2 3 4 5 6 7 8 10 |
9 |
| Sample Input 4 | Sample Output 4 |
|---|---|
8 8 7 6 5 4 3 2 1 |
1 |
