Stonks

Un investitor urmărește evoluția prețului unei acțiuni timp de $N$ zile consecutive. Prețul acțiunii în ziua $i$ este dat de valoarea $A_i$.

Dorind să facă o analiză retroactivă, investitorul încearcă să identifice „perioada de aur”, adică intervalul de zile în care ar fi putut obține cel mai mare profit net.

O perioadă este definită printr-un interval de zile $[Z_1, Z_2]$, unde $1 \leq Z_1 \leq Z_2 \leq N$.

Pentru un astfel de interval:

• Se determină prețul maxim atins în interval:
  $$PretMax = \max(A_{Z_1}, A_{Z_1+1}, \dots, A_{Z_2})$$
• Se determină prețul minim atins în interval:
  $$PretMin = \min(A_{Z_1}, A_{Z_1+1}, \dots, A_{Z_2})$$

Câștigul potențial brut al perioadei este:

Totuși, banca percepe o taxă de administrare egală cu numărul de zile scurse între începutul și sfârșitul perioadei, adică:

Astfel, profitul net al unei perioade este:

Cerință

Determinați profitul net maxim care s-ar fi putut obține alegând în mod optim o perioadă $[Z_1, Z_2]$.

Date de intrare

Fișierul de intrare stonks.in conține:

• Pe prima linie, un număr întreg $N$, reprezentând numărul de zile.
• Pe a doua linie, $N$ numere întregi $A_1, A_2, \dots, A_N$, reprezentând prețurile acțiunii în fiecare zi.

Date de ieșire

Fișierul de ieșire stonks.out va conține un singur număr întreg, reprezentând profitul net maxim posibil.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $0 \leq A_i \leq 10^9$
• $1 \leq Z_1 \leq Z_2 \leq N$

Exemplu

stonks.in

5
5 3 4 1 2

stonks.out

2

Explicație

Pentru intervalul $[3,4]$:

Acesta este profitul net maxim posibil.