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.

#include <bits/stdc++.h>


using namespace std;

ifstream fin("secvente.in");
ofstream fout("secvente.out");

int main()
{
    const int Inf = 0x3f3f3f3f;
    int a[100002];  
    int minim[100002];  
    int maxim[100002];  
    int n; 
    cin >> n;
    maxim[0] = -Inf;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        if (a[i] > maxim[i - 1])
            maxim[i] = a[i];
        else
            maxim[i] = maxim[i - 1];
    }
    
    minim[n + 1] = Inf;
    for (int i = n; i >= 1; --i)
        if (a[i] < minim[i + 1])
            minim[i] = a[i];
        else
            minim[i] = minim[i + 1];        
    int dif, dif_max = -Inf;
    for (int i = 1; i < n; ++i)
    {
        dif = maxim[i] - minim[i + 1];
        if (dif > dif_max)
            dif_max = dif;
    }
    cout << dif_max;
    
    fin.close();
    fout.close();
    
    return 0;
}