Мансұр ескі ойын-сауық саябағын сатып алған кезде, оның назарын бірден саябақтың басты мақтанышы — алып америкалық төбешік аударды. Бұл төбешік бүкіл саябақты бойлай созылып, әрқайсысының биіктігі \(a_i\) болатын \(n\) болат тіректен тұрды. Дәл осы тіректер трассаның пішінін анықтайды — вагон қай жерде жылдамдық алады, ал қай жерде баяу көтеріледі.

Мансұр төбешіктен бір рет сырғанап көрді де, бір нәрсенің дұрыс еместігін түсінді: көтерілу бөліктері тым ұзын, ал түсу тым тез әрі әсерсіз еді. Аттракционды құтқару үшін ол сәулетші достарын — Исатай мен Алдиярды шақырды. Бірге олар трассаны жетілдіру үшін кейбір тіректерді алып тастауды шешті, осылайша төбешік шын мәнінде қызық болмақ.

Тіректерді алып тастағаннан кейін қалғандары бастапқы ретімен өзара байланысады. Дәл осы тіректер арқылы вагонның жаңа бағыты өтеді.

Сәулетшілер төбешіктің қызықтылық деңгейін өлшеудің тәсілін ұсынды. Таңдалған бағыттағы көрші екі тірек биіктіктері \(a_i\) және \(a_{i+1}\) болғанда, олардың «ләззат» мөлшері келесідей есептеледі:

• егер \(a_i > a_{i+1}\) болса, трасса төмен түседі де, «ләззат» мөлшеріне \((a_i - a_{i+1})^2\) ұпай қосылады — өйткені түсулер қызықты;

• егер \(a_i < a_{i+1}\) болса, трасса жоғары көтеріледі де, «ләззат» мөлшерінен \((a_{i+1} - a_i)^2\) ұпай алынады — өйткені көтерілу шаршатады және қызығушылықты төмендетеді;

• егер \(a_i = a_{i+1}\) болса, биіктік өзгермейді, және үлес \(0\)-ге тең.

Маршруттың жалпы қызықтылығы — көрші тіректердің барлық жұптары бойынша осы үлестердің қосындысы. Мансұр бұл қосындыны барынша арттыру үшін кейбір (мүмкін ешқайсысын емес) тіректерді алып тастай алады.

Егер ең жақсы таңдаудан кейін де қызықтылық теріс мәнге тең болса, Мансұр аттракционды уақытша жабуға шешім қабылдайды — бұл жағдайда нәтиже \(0\) деп есептеледі.

Достарына көмектесіп, тіректердің кейбірін алып тастау арқылы алынатын ең үлкен мүмкін «ләззат» қосындысын табыңыз.

Енгізу

Бірінші жолда бір бүтін сан \(n\) — тіректер саны берілген. \((1 \le n \le 10^6)\).

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) берілген, мұнда \(a_i\) — \(i\)-ші тіректің биіктігі. \((1 \le a_i \le 10^6)\).

Шығару

Бір бүтін сан шығарыңыз — төбешіктің мүмкін болатын ең үлкен қызықтылығы. Егер ешбір нұсқа оң нәтиже бермесе, 0 шығарыңыз.

Бағалау жүйесі

Мысалдар

Енгізу 1

3
3 5 4

Жауап 1

1

Енгізу 2

5
1 2 2 3 4

Жауап 2

0

Енгізу 3

7
5 1 2 2 2 5 1

Жауап 3

22

Ескертпелер

Бірінші мысалға ескерту. Барлық мүмкін жұптардың үлесін есептейік:

• \((3,5)\) — көтерілу \(\rightarrow\) үлес \(-(5-3)^2 = -4\);

• \((5,4)\) — түсу \(\rightarrow\) үлес \(+(5-4)^2 = +1\);

• \((3,4)\) — көтерілу \(\rightarrow\) үлес \(-(4-3)^2 = -1\).

Сонда бізде келесі нұсқалар бар:

• Барлығын қалдыру: [\(3,5,4\)] \(\rightarrow\) қосынды \(-4 + 1 = -3\);

• Жұпты қалдыру: [\(3,5\)] \(\rightarrow -4\);

• Жұпты қалдыру: [\(3,4\)] \(\rightarrow -1\);

• Жұпты қалдыру: [\(5,4\)] \(\rightarrow 1\);

• Бір тіректі қалдыру (немесе бос) \(\rightarrow 0\).

Максималды «ләззат» мөлшері [\(5,4\)] үшін қол жеткізіледі — қосындысы \(1\).

Екінші мысалға ескерту. Бастапқы қатарына ұлғаю тәртібі тән (неубывающая). Оның кез келген ішкі реттілігі де ұлғаюшы болады, демек таңдалған маршрут бойынша кез келген көрші жұп үшін \(a_i \le a_{i+1}\):

• егер қатты көтерілу болса \(a_i < a_{i+1}\) — үлес теріс: \(-(a_{i+1}-a_i)^2 < 0\);

• егер тең болса \(a_i = a_{i+1}\) — үлес \(0\).

Оң үлес (құлдырау) мүмкін емес. Сондықтан минусқа түспеу үшін оңтайлысы — бір элемент таңдау (немесе тең жұптар, немесе ештеңе), бұл \(0\) береді.