Hide

Problem G
Svifdrekamaður

/problems/iceland.svifdrekamadur/file/statement/is/img-0001.jpg
Hinn mikli svifdrekamaður, Sigurður Jens, er að fara að halda sýningu í Reykjavíkurborg. Eins og allir vita er bara ein húsaröð í Reykjavíkurborg og sú húsaröð samanstendur af $n$ húsum. Við getum því táknað Reykjavíkurborg með lista af $n$ heiltölum $a_1, a_2, \dotsc , a_ n$ þar sem hver tala $a_ i$ táknar hæð $i$-tu byggingarinnar í metrum. Fjarlægð milli $i$-ta hússins og $j$-ta hússins er einfaldlega munurinn á tölunum $i$ og $j$ (sem má einnig rita $\mid i - j \mid $).

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, \dotsc , 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

Hópur

Stig

Takmarkanir

1

20

$1 \le n \le 100$, öll $a_ i$ mismunandi

2

25

$1 \le n \le 5\, 000$, öll $a_ i$ mismunandi

3

25

$1 \le n \le 10^5$, $1 \le a_ i \le 100$

4

30

Engar frekari takmarkanir

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

Please log in to submit a solution to this problem

Log in