#include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll MOD = 998244353; class ModInt{ public: ll v; ModInt(ll _v = 0){ v = _v; } ModInt operator+(ll n){ return ModInt((v+n)%MOD); } ModInt operator-(ll n){ return ModInt((v-n+MOD)%MOD); } ModInt operator*(ll n){ return ModInt((v*n)%MOD); } ModInt operator/(ll n){ return ModInt((ModInt(n).inv()*v).v%MOD); } void operator+=(ll n){ v = (v+n)%MOD; } void operator-=(ll n){ v = (v-n+MOD)%MOD; } void operator*=(ll n){ v = (v*n)%MOD; } ModInt operator+(ModInt n){ return ModInt((v+n.v)%MOD); } ModInt operator-(ModInt n){ return ModInt((v-n.v+MOD)%MOD); } ModInt operator*(ModInt n){ return ModInt((v*n.v)%MOD); } ModInt operator/(ModInt n){ return ModInt((n.inv()*v).v%MOD); } void operator+=(ModInt n){ v = (v+n.v)%MOD; } void operator-=(ModInt n){ v = (v-n.v+MOD)%MOD; } void operator*=(ModInt n){ v = (v*n.v)%MOD; } void operator=(ModInt n){ v = n.v; } void operator=(ll n){ v = n; } ModInt inv(){ if(v == 1) return ModInt(1); else return ModInt(MOD-ModInt(MOD%v).inv().v*(MOD/v)%MOD); } }; ostream& operator<<(ostream& os, const ModInt& m){ os << m.v; return os; } istream & operator >> (istream &in, ModInt &m){ in >> m.v; return in; } template struct segtree{ int n; T UNIT; vector dat; T (*calc)(T, T); segtree(int n_, T unit, T (*_calc)(T, T)){ UNIT = unit; calc = _calc; n = 1; while(n < n_) n *= 2; dat = vector(2*n); for(int i = 0; i < 2*n; i++) dat[i] = UNIT; } void insert(int k, T a){ dat[k+n-1] = a; } void update_all(){ for(int i = n-2; i >= 0; i--){ dat[i] = calc(dat[i*2+1], dat[i*2+2]); } } //k番目の値(0-indexed)をaに変更 void update(int k, T a){ k += n-1; dat[k] = a; while(k > 0){ k = (k-1)/2; dat[k] = calc(dat[k*2+1], dat[k*2+2]); } } //[a, b) //区間[a, b]へのクエリに対してはquery(a, b+1)と呼ぶ T query(int a, int b, int k=0, int l=0, int r=-1){ if(r < 0) r = n; if(r <= a || b <= l) return UNIT; if(a <= l && r <= b) return dat[k]; else{ T vl = query(a, b, k*2+1, l, (l+r)/2); T vr = query(a, b, k*2+2, (l+r)/2, r); return calc(vl, vr); } } }; ModInt add(ModInt x, ModInt y){ return x+y; } int n; vector a; // 差がm以下のマウンテン配列の個数 ModInt count(int m){ vector dp(n+1, ModInt(0)); segtree sgt(n, ModInt(0), add); set rem; for(int i = 0; i < n; i++){ rem.insert(i); } if(a[0]-a[1] > m) return ModInt(0); dp[0] = 2; dp[1] = 2; sgt.update(0, ModInt(2)); sgt.update(1, ModInt(2)); for(int i = 2; i < n; i++){ if(a[i-1]-a[i] > m) return ModInt(0); if(a[0]-a[i] <= m){ dp[i] = sgt.query(0, i); }else{ int l = 0, r = i-1; while(r-l > 1){ int c = (l+r)/2; if(a[c]-a[i] > m) l = c; else r = c; } dp[i] = sgt.query(r, i); if(r == i-1){ sgt.update(i-1, ModInt(0)); } } sgt.update(i, dp[i]); } return dp[n-1]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> n; a.assign(n, 0); for(int i = 0; i < n; i++){ cin >> a[i]; } reverse(a.begin(), a.end()); vector cnt(2501, ModInt(0)); for(int i = 1; i <= 2500; i++){ cnt[i] = count(i); } ModInt ans = 0; for(int i = 1; i <= 2500; i++){ ans += (cnt[i]-cnt[i-1])*i; // if((cnt[i]-cnt[i-1]).v != 0) cout << i << ':' << cnt[i] << '-' << cnt[i-1] << endl; } cout << ans << endl; }