Let us define \(\text{dp}_i\) as the answer for the first \(i\) terms of \(A\), \(A'=(A_1,A_2,\ldots,A_i)\). Then the following relation holds (where \(\text{dp}_0=1\)).

• \(\text{dp}_i=\sum_{j=0}^{i-1} \text{dp}_j \times (\max(\{A_{j+1},A_{j+2},\ldots,A_i\})-\min(\{A_{j+1},A_{j+2},\ldots,A_i\}))\)

The complexity of such DP (Dynamic Programming) costs \(O(N^2)\) when computed naively, but we can reduce it to \(O(N)\) with some tweaks.

First, let us divide the recurrence relation above into \(\max\) and \(\min\).

• \(\text{dp}_i=\sum_{j=0}^{i-1} \text{dp}_j \times \max(\{A_{j+1},A_{j+2},\ldots,A_i\}) - \sum_{j=0}^{i-1} \text{dp}_j \times \min(\{A_{j+1},A_{j+2},\ldots,A_i\})\)

Such form of transition, namely the form “\(\sum_{j=0}^{i-1} \text{dp}_j \times \max(\{A_{j+1},A_{j+2},\ldots,A_i\})\)” is very suited for optimizations. We may use a data structure like a stack to update \(\max(\{A_{j+1},A_{j+2},\ldots,A_i\})\) accordingly while computing the cumulative sums, so that the \(\text{dp}\) can be computed in a linear time. The \(\min\) part is almost the same.

Specifically, load a pair of the following two values, and update the differences properly.

• The value of \(\max(\{A_{j+1},A_{j+2},\ldots,A_i\})\)
• The sum of \(\text{dp}_k\) for all \(k\) such that the value of \(\max(\{A_{k+1},A_{k+2},\ldots,A_i\})\) is equal to the value described above

Sample code (C++)

#include<bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using ll = long long;

const ll MOD = 998244353;

int main(){
	int N; cin >> N;
	vector<ll> A(N);
	for(int i=0; i<N; i++) cin >> A[i];
	vector<ll> dp(N+1);
	dp[0] = 1;
	std::stack<ll> max, min, max_v, min_v;
	ll max_sum = 0, min_sum = 0;
	for(int i=0; i<N; i++){
		// max
		{
			ll sum_v = dp[i];
			while(!max.empty() && max.top() < A[i]){
				max_sum -= max_v.top()*max.top();
				sum_v += max_v.top();
				max_sum %= MOD;
				sum_v %= MOD;
				max.pop();
				max_v.pop();
			}
			max_sum += sum_v*A[i];
			max_sum %= MOD;
			max.push(A[i]);
			max_v.push(sum_v);
		}
		// min
		{
			ll sum_v = dp[i];
			while(!min.empty() && min.top() > A[i]){
				min_sum -= min_v.top()*min.top();
				sum_v += min_v.top();
				min_sum %= MOD;
				sum_v %= MOD;
				min.pop();
				min_v.pop();
			}
			min_sum += sum_v*A[i];
			min_sum %= MOD;
			min.push(A[i]);
			min_v.push(sum_v);
		}
		dp[i+1] = max_sum-min_sum;
		dp[i+1] %= MOD;
	}
	ll ans = dp[N];
	if(ans < 0) ans += MOD;
	cout << ans << endl;
}

Note that there are alternative way to optimize \(\text{dp}\) utilizing the structure of Cartesian Tree (See also https://atcoder.jp/contests/arc115/tasks/arc115_e )