proeminenta

#include <fstream>
using namespace std;
#define NMax 1000005
long long int N,C,s,a[NMax];

long long int min(long long int i,long long int j)
{
    if(i<j)
        return i;
    return j;
}

long long int peak[NMax],valley[NMax],top=-1; /// peak este stiva de varfuri
/// valley retine cele mai adanci vai
long long int prom[2][NMax]; /// proeminenta la stanga varfului de pe pozita i este prom[0][i]
/// si la dreapta este prom[0][n-1-i] datorita oglindirii

void popTop()
{ /// eliminam un varf din stiva, actualizam cea mai adanca vale din dreapta daca e cazul
    if(top<0)
        return;
    if(top>=1&&valley[top-1]>valley[top])
        valley[top-1]=valley[top];
    --top;
}

int main()
{
    ifstream f("proeminenta.in");
    ofstream g("proeminenta.out");
    f>>C>>N;
    for(int i=0;i<N;++i)
    {
        f>>a[i];
        if(i>0&&a[i]==a[i-1])
            --i,--N; /// eliminam duplicatele
    }
    if(C==1)
    {
        for(int i=1;i<N-1;++i)
        if(a[i-1]<a[i]&&a[i]>a[i+1])
            ++s; /// este varf
        g<<s<<'\n';
        return 0;
    }
    for(int d=0;d<=1;++d)
    { /// d=0 va fi parcurgerea stanga-dreapta,si d=1
      /// dupa oglindire,adica dreapta -stanga
        for(int i=1;i<N-1;++i)
        {
            if(a[i-1]<a[i]&&a[i]>a[i+1]) { // este varf
            prom[d][i]=a[i];
            while(top>=0&&a[peak[top]]<=a[i]) /// elimin varfurile mai mici din stiva pe rand
                popTop();
            if(top>=0&&a[peak[top]]>a[i])
                prom[d][i]=a[i]-valley[top]; /// am gasit primul varf mai mare din stanga
            peak[++top]=i;
            valley[top]=a[i]; /// adaugam noul varf
            }
            if(top>=0&&valley[top]>a[i])
                valley[top]=a[i];
        }
        for(int i=0;i<N/2;++i) /// oglindim altitudinile
            swap(a[i],a[N-1-i]);
        top=-1;
    }
    for(int i=1;i<N-1;++i)
        if(a[i-1]<a[i]&&a[i]>a[i+1])
            if(prom[0][i]>prom[1][N-1-i]) /// retinem maximul in prom[0][i]
                prom[0][i]=prom[1][N-1-i];
    for(int i=1;i<N-1;++i)
        if(prom[0][i]>0)
            g<<prom[0][i]<<' '; /// si il afisam
    g<<'\n';
    return 0;
}