Se consideră un șir a[1], a[2], …, a[n] de numere întregi.

Cerința

Să se determine diferența maximă de forma a[i] - a[j], unde 1 ≤ i < j ≤ n.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi șirul de n numere întregi, separate prin spații.

Date de ieșire

Programul va afișa pe ecran un singur număr întreg reprezentând diferența maximă cerută.

Restricții și precizări

• 1 ≤ n ≤ 100 000
• -1 000 000 000 ≤ a[i] ≤ 1 000 000 000

Exemplu:

Intrare

8
3 5 2 7 6 3 9 8

Ieșire

4

Explicație

Diferența maximă 4 se obține din a[4]-a[6]=7-3=4.