\(dp[i][j]=i\) 番目までの部員までで、\(j\) 番の部員が最後にくるような昇順に並べられた部分列を作ったとき、コストの最小値（ただし、\(j+1\) 番目以降の部員を消すコストは考えない）

とする DP を考えます。 このとき、遷移は次のようになります。

\[ \begin{aligned} dp[i][j]&\leftarrow dp[i-1][j]\\ dp[i][i]&\leftarrow dp[i-1][j]+a[j+1]+a[i-1]\ (\mathrm{iff}\ a[j]<a[i]) \end{aligned} \]

この式を眺めると、\(dp[i][i]\) 以外の値は前と変わらないので、\(dp[i][i]\) だけを高速に計算できればよいことがわかります。 これは、\(dp[x][j]+a[j+1]\) の値を Segment Tree などのデータ構造に \(a[j]\) の値と対応させて持ち、\(dp[i][i]\) を求める際には「\(a[j]<a[i],j<i\) を満たすような \(j\) の、\(dp[i-1][j]+a[j+1]\) の最小値」を求めればよいです。 計算量は \(O(N\log N)\) になります。

#include <iostream>
#include <atcoder/segtree>
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define REP(i, n) for (int i = 1; i <= int(n); i++)
using lint = long long int;
constexpr int INF = 1e9;
constexpr lint LINF = 1e18;
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return true;
	}
	return false;
}
static int RMiQ_nodef(int lhs, int rhs) {
	return std::min(lhs, rhs);
}
static int RMiQ_ef(){
	return INF;
}
using RMiQ = atcoder::segtree<int, RMiQ_nodef, RMiQ_ef>;
int N, A[200010];
int main() {
	std::cin >> N;
	rep(i, N) std::cin >> A[i];
	A[N] = N + 1;
	RMiQ st(N + 2);
	st.set(0, A[0]);
	st.set(A[0], A[1]);
	REP(i, N) {
		int x = st.prod(0, A[i]) + A[i - 1];
		if (A[i - 1] < A[i]) chmin(x, st.get(A[i - 1]) - A[i]);
		st.set(A[i], x + A[i + 1]);
	}
	std::cout << st.get(N + 1) << std::endl;
	return 0;
}