0-indexed で考えます。この問題は以下のように言い換えることができます。

これは辺コストを $-1$ 倍することで最短パスの問題へ帰着できます。以降はこれを考えます。ここで、 $c \left( i, j \right) = \min_{i \leq k < j} \left( a_k \right) - \max_{i \leq k < j} \left( a_k \right)$ を $i$ から $j$ への辺のコストとします。
動的計画法を考えます。 $\mathrm{dp}[j]$ を頂点 $j$ までの最短コストとして、遷移は $\mathrm{dp}[j] = \min_{i < j} \left( \mathrm{dp}[i] + c \left( i ,j \right) \right)$ です。

ここで、 \(i < j < k < l\) について \(c \left(i,l \right) + c \left( j,k \right) \geq c \left( i, k \right) + c \left( j,l \right)\) が成立します。

このような $c$ は Monge 性を満たしています。
Monge 性を満たしているグラフは高速に計算できることが知られています。詳細は以下の資料に譲ります。

下の実装例の場合、 \(c\) を segtree を用いて \(O \left( \log N \right)\) で求めているので、全体の計算量は \(O \left( N \log^2 N \right)\) です。
実装例

#include <iostream>
using namespace std;

#include <atcoder/segtree>
using namespace atcoder;

using P = pair<long long,long long>;

P op(P a,P b){
  return {max(a.first,b.first),min(a.second,b.second)};
}
P e(){
  return {-1e18,1e18};
}

// https://noshi91.hatenablog.com/entry/2023/02/18/005856
// T は辺コストの型
// cost(i,j) は頂点 i -> 頂点 j へのコスト(型 T)を返す関数
// 頂点番号は 0-ind
// 返り値は配列 dist で dist[i] が 0 -> i の最小コストに相当
// a[i][j] を j -> i を最後にするコスト dist[j]+cost(j,i) とする(j < i)
// a[i] が最小値を取るような j が欲しい これを amin で管理
template <typename T,typename F>
vector<T> monge_shortest_path(int n,T inf,const F & cost){
  vector<T> dist(n,inf);
  dist[0]=0;
  vector<int> amin(n,0);

  auto check=[&](int i,int k){
    // k -> i に行くもので暫定の最小値を更新できるかを確認
    if(k>=i)return;
    auto dist2=dist[k]+cost(k,i);
    if(dist2<dist[i]){
      dist[i]=dist2;
      amin[i]=k;
    }
  };

  auto subsolve=[&](auto& subsolve,int l,int r){
    // (l,r] について dist を計算する
    if(r-l==1)return;
    int m=(l+r)/2;
    for(int k=amin[l];k<=amin[r];k++)check(m,k);
    subsolve(subsolve,l,m);
    for(int k=l+1;k<=m;k++)check(r,k);
    subsolve(subsolve,m,r);
  };

  check(n-1,0);
  subsolve(subsolve,0,n-1);
  return dist;
}

int main(){
  int n;cin>>n;
  vector<long long> a(n);
  for(int i=0;i<n;i++)cin>>a[i];

  segtree<P,op,e> seg(n);
  for(int i=0;i<n;i++)seg.set(i,{a[i],a[i]});

  auto cost=[&](int i,int j){
    auto [mx,mn]=seg.prod(i,j);
    return mn-mx;
  };

  auto dist=monge_shortest_path<long long>(n+1,1e18,cost);
  cout<<-dist[n]<<endl;
}