#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

const int maxn=1e6+;

const int inf=<<;

int size[maxn];

int top[maxn];

int dfsx[maxn];

int son[maxn];

int father[maxn];

struct node

{

    int to;

    int next;

}way[maxn<<];

struct node1

{

    int max;

    int min;

    int ans,ans1;

    node1()

    {

        ans=ans1=max=;

        min=inf;

    }

}

struct node2

{

    int l,r,ls,rs;

    int min,max;

    int ans,ans1;

    int lazy;

}tree[maxn<<];

int add(int x,int y)

{

    way[++tot].next=head[x];

    way[tot].to=y;

    head[x]=tot;

}

int dfs1(int x)

{

    size[x]=;

    for(int i=head[x];i;i=way[i].next)

    {

        int to=way[i].to;

        if(father[x]==to)

        {

            continue;

        }

        deep[to]=deep[x]+;

        father[to]=x;

        dfs1(to);

        size[x]+=size[to];

        if(size[to]>size[son[x]])

        {

            son[x]=to;

        }

    }

}

int dfs2(int x,int tp)

{

    id[x]=++cnt;

    top[x]=tp;

    value[cnt]=a[x];

    if(son[x])

    {

        dfs2(son[x],tp);

    }

    for(int i=head[x];i;i=way[i].next)

    {

        int to=way[i].to;

        if(to==fa||to==son[x])

        {

            continue;

        }

        dfs2(to,to);

    }

}

inline int pushup(int x)

{

    tree[x].ans=max(tree[tree[x].rs].max-tree[tree[x].ls].min,max(tree[tree[x].ls].ans,tree[tree[x].rs].ans));

    tree[x].ans1=max(tree[tree[x].ls].max-tree[tree[x].rs].min,max(tree[tree[x].ls].ans1,tree[tree[x].rs].ans1);

    tree[x].max=max(tree[tree[x].ls].max,tree[tree[x].rs].max);

    tree[x].min=min(tree[tree[x].ls].min,tree[tree[x].rs].min);

}

int build(int x,int l,int r)

{

    x=++cnt;

    tree[x].l=l;

    tree[x].r=r;

    if(l==r)

    {

        tree[x].min=tree[x].max=value[l];

        tree[x].ans=tree[x].ans1=;

        return ;

    }

    int mid=(l+r)>>;

    build(tree[x].ls,l,mid);

    build(tree[x].rs,mid+,r);

    pushup(x);

}

inline pushdown(int x)

{

    if(!tree[x].lazy)

    {

        return ;

    }

    tree[tree[x].ls].lazy+=tree[x].lazy;

    tree[tree[x].rs].lazy+=tree[x].lazy;

    tree[tree[x].ls].max+=tree[x].lazy;

    tree[tree[x].rs].max+=tree[x].lazy;

    tree[tree[x].ls].min+=tree[x].lazy;

    tree[tree[x].rs].min+=tree[x].lazy;

    tree[x].lazy=;

}

node1 pushup1(node1 tmp1,node1 tmp2)

{

    node1 ans1;

    ans1.ans=max(tmp2.max-tmp1.min,max(tmp1.ans,tmp2.ans));

    ans1.ans1=max(tmp1.max-tmp2.min,max(tmp1.ans1,tmp2.ans1));

    ans1.min=min(tmp1.min,tmp2.min);

    ans1.max=max(tmp1.max,tmp2.max);

    return ans1;

}

}

node1 update(int x,int l,int r,int val)

{

    if(l<=tree[x].l&&r>=tree[x].r)

    {

        tree[x].lazy+=val;

        tree[x].max+=val;

        tree[x].min+=val;

        node1 ttt;

        ttt.max=tree[x].max;

        ttt.min=tree[x].min;

        ttt.ans=tree[x].ans;

        ttt.ans1=tree[x].ans1;

        return ttt;

    }

    int mid=(tree[x].l+tree[x].r)>>;

    node1 ttt1;

    node1 ttt2;

    pushdown(x);

    if(l<=mid)

    {

        ttt1=update(tree[x].ls,l,r,val);

    }

    if(r>mid)

    {

        ttt2=update(tree[x].rs,l,r,val);

    }

    pushup(x);

    return pushup1(ttt1,ttt2);

}

int main()

{

    return ;

 }