Hide

Problem G
Svifdrekamaður

Languages en is

/problems/svifdrekamadur/file/statement/en/img-0001.jpg

The great kiteman, Sigurður Jens, is going to hold a show in Reykjavík. As everyone knows, there is only one row of buildings in Reykjavík and that row consists of

n

houses. We can thus model Reykjavík using a list of

n

integers

a_{1}, a_{2}, \dots, a_{n}

where each value

a_{i}

denotes the height of the

i

-th building, given in meters. The distance between the

i

-th house and the

j

-th house is simply the difference between

i

and

j

(which can be written as

∣ i - j ∣

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 \leq n \leq 10^{5}$ . The next line contains $n$ integers separated by spaces, $a_{1}, a_{2}, \dots, a_{n}$ . For each value $a_{i}$ it is guaranteed that $1 \leq a_{i} \leq 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 \leq n \leq 100$ , all $a_{i}$ are distinct
2	25	$1 \leq n \leq 5 000$ , all $a_{i}$ are distinct
3	25	$1 \leq n \leq 10^{5}$ , $1 \leq a_{i} \leq 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

Problem GSvifdrekamaður

Input

Output

Scoring

Problem G
Svifdrekamaður