Problem G
Svifdrekamaður

Eins og allir vita er svifdrekamaðurinn Sigurður Jens frægur fyrir að svífa milli bygginga. Þó hann sé rosalega fær svifdrekamaður þá getur hann ekki hækkað flugið frá upphafshæð sinni. Hann verður því alltaf að lenda í lægri hæð en hann hóf svifið.

Til að forðast vandræði með að mögulega klessa á byggingar þá hefur Reykjavíkurborg sett þá reglu að allar byggingar á milli byggingarinnar þar sem hann byrjar svifið og byggingarinnar þar sem hann endar svifið þurfa að vera lægri en þær. Við getum því sagt að hann má einungis svífa á milli tveggja bygginga $i,j$ svo lengi sem $a_i>a_j$ og allar byggingar á milli $i$ og $j$ eru minni en $a_i$ og $a_j$.

Sigurður Jens vill að sýningin hans í Reykjavíkurborg verði eins spennandi og mögulegt er, en spenna svifs er skilgreind sem vegalengdin sem svifið nær yfir. Hann þarf því að finna bestu tvær byggingarnar til að svífa á milli. Af öllum mögulegum sýningum sem Sigurður Jens svifdrekamaður gæti boðið uppá, geturðu sagt hvað er hámarks spenna sem hann gæti náð?

Inntak

Fyrsta lína inniheldur eina heiltölu $1\le n\le {10}^5$. Næsta lína inniheldur $n$ heiltölur aðskildar með bili, $a_1,a_2,\dots ,a_n$. Fyrir hverja tölu $a_i$ gildir $1\le a_i\le {10}^9$.

Úttak

Skrifaðu út eina heiltölu, hæstu mögulegu spennu sem hægt er að fá úr sýningu. Ef engar sýningar eru mögulegar skal skrifa út $0$.

Stigagjöf

1
20

0

10
8 12 6 18 4 10 18 7 8 16

3

10
9 1 2 3 4 5 6 7 8 10

9

8
8 7 6 5 4 3 2 1

1