/* #region header */ #ifdef LOCAL #include "cxx-prettyprint-master/prettyprint.hpp" #define debug(x) cout << x << endl #else #define debug(...) 42 #endif #pragma GCC optimize("Ofast") #include using namespace std; // types using ll = long long; using ull = unsigned long long; using ld = long double; typedef pair Pl; typedef pair Pi; typedef vector vl; typedef vector vi; typedef vector vc; template using mat = vector>; typedef vector> vvi; typedef vector> vvl; typedef vector> vvc; template struct modint { int x; modint() : x(0) {} modint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} modint& operator+=(const modint& p) { if ((x += p.x) >= mod) x -= mod; return *this; } modint& operator-=(const modint& p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } modint& operator*=(const modint& p) { x = (int)(1LL * x * p.x % mod); return *this; } modint& operator/=(const modint& p) { *this *= p.inverse(); return *this; } modint operator-() const { return modint(-x); } modint operator+(const modint& p) const { return modint(*this) += p; } modint operator-(const modint& p) const { return modint(*this) -= p; } modint operator*(const modint& p) const { return modint(*this) *= p; } modint operator/(const modint& p) const { return modint(*this) /= p; } bool operator==(const modint& p) const { return x == p.x; } bool operator!=(const modint& p) const { return x != p.x; } modint inverse() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return modint(u); } modint pow(int64_t n) const { modint ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream& operator<<(ostream& os, const modint& p) { return os << p.x; } friend istream& operator>>(istream& is, modint& a) { int64_t t; is >> t; a = modint(t); return (is); } static int get_mod() { return mod; } }; // abreviations #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define rep_(i, a_, b_, a, b, ...) for (ll i = (a), max_i = (b); i < max_i; i++) #define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define rrep_(i, a_, b_, a, b, ...) \ for (ll i = (b - 1), min_i = (a); i >= min_i; i--) #define rrep(i, ...) rrep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define srep(i, a, b, c) for (ll i = (a), max_i = (b); i < max_i; i += c) #define SZ(x) ((int)(x).size()) #define pb(x) push_back(x) #define eb(x) emplace_back(x) #define mp make_pair //入出力 #define print(x) cout << x << endl template ostream& operator<<(ostream& os, const vector& v) { for (auto& e : v) cout << e << " "; cout << endl; return os; } void scan(int& a) { cin >> a; } void scan(long long& a) { cin >> a; } void scan(char& a) { cin >> a; } void scan(double& a) { cin >> a; } void scan(string& a) { cin >> a; } template void scan(vector& a) { for (auto& i : a) scan(i); } #define vsum(x) accumulate(all(x), 0LL) #define vmax(a) *max_element(all(a)) #define vmin(a) *min_element(all(a)) #define lb(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define ub(c, x) distance((c).begin(), upper_bound(all(c), (x))) // functions // gcd(0, x) fails. ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } template bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } template T mypow(T x, ll n) { T ret = 1; while (n > 0) { if (n & 1) (ret *= x); (x *= x); n >>= 1; } return ret; } ll modpow(ll x, ll n, const ll mod) { ll ret = 1; while (n > 0) { if (n & 1) (ret *= x); (x *= x); n >>= 1; x %= mod; ret %= mod; } return ret; } uint64_t my_rand(void) { static uint64_t x = 88172645463325252ULL; x = x ^ (x << 13); x = x ^ (x >> 7); return x = x ^ (x << 17); } int popcnt(ull x) { return __builtin_popcountll(x); } // graph template template struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge& operator=(const int& x) { to = x; return *this; } bool operator<(const edge& r) const { return cost < r.cost; } operator int() const { return to; } }; template using Edges = vector>; template using WeightedGraph = vector>; using UnWeightedGraph = vector>; struct Timer { clock_t start_time; void start() { start_time = clock(); } int lap() { // return x ms. return (clock() - start_time) * 1000 / CLOCKS_PER_SEC; } }; /* #endregion*/ // constant #define inf 1000000000ll #define INF 4000000004000000000LL #define mod 998244353ll using mint = modint; typedef vector vmint; typedef vector> vvmint; #define endl '\n' const long double eps = 0.000000000000001; const long double PI = 3.141592653589793; // O(√m) // a^x = b (mod m)を満たすxの最小値(なければ-1) // x = p√m+r, p, r < √m // a^r = bA^p ll modlog(ll a, ll b, ll m) { //√m ll sqrt_m = sqrt(m) + 2; // a^-√m ll A = modpow(a, (mod - 2), mod); A = modpow(A, sqrt_m, mod); // a^0,...,a^√m unordered_map a_pows; ll a_pow = 1; rep(i, sqrt_m + 1) { a_pows[a_pow] = i; a_pow *= a; a_pow %= m; } // A^0,...,A^√m ll A_pow = 1; rep(i, sqrt_m + 1) { if (a_pows.count(A_pow * b)) { return i * sqrt_m + a_pows[A_pow * b]; } A_pow *= A; A_pow %= m; } return -1; } int64_t euler_phi(int64_t n) { int64_t ret = n; for (int64_t i = 2; i * i <= n; i++) { if (n % i == 0) { ret -= ret / i; while (n % i == 0) n /= i; } } if (n > 1) ret -= ret / n; return ret; } /** * @brief UnionFind * @docs docs/UnionFind.md */ struct UnionFind { vector data; // sizes of sets UnionFind(int sz) : data(sz, -1) {} bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return true; } int find(int k) { if (data[k] < 0) return k; return data[k] = find(data[k]); } int size(int k) { return (-data[find(k)]); } bool same(int x, int y) { return find(x) == find(y); } }; template struct BIT { vector data; BIT(int sz) { data.assign(++sz, 0); } //[0, k) T sum(int k) { T ret = 0; for (; k > 0; k -= k & -k) ret += data[k]; return (ret); } void add(int k, T x) { for (++k; k < data.size(); k += k & -k) data[k] += x; } // 0-indexedでk番目の値を返す。 int search(long long k) { ++k; int res = 0; int N = 1; while (N < (int)data.size()) N *= 2; for (int i = N / 2; i > 0; i /= 2) { if (res + i < (int)data.size() && data[res + i] < k) { k = k - data[res + i]; res = res + i; } } return res; } // for debug void show() { rep(i, SZ(data) - 1) cout << sum(i + 1) - sum(i) << ' '; cout << endl; } }; int main() { cin.tie(0); ios::sync_with_stdio(0); cout << setprecision(30) << fixed; int n; cin >> n; vl a(n); scan(a); mint ans = 0; mint prev = 0; rep(m, 2501) { vmint dp(n); dp[n - 1] = 1; vmint cum(n + 1); BIT bit(n); bit.add(n - 1, dp[n - 1]); rrep(i, 0, n - 1) { int j = min(n - 1, (int)ub(a, a[i] + m)); dp[i] += bit.sum(j) - bit.sum(i + 1); // rep(j, i + 1, n - 1) { // // if (a[i] + m >= a[j + 1]) dp[i] += dp[j]; // } if (a[i] + m >= a.back() && i + 1 != n - 1) dp[i] += dp.back(); bit.add(i, dp[i]); } mint res = 0; rep(i, n) { res += dp[i]; if (i < n - 1 && a[i] + m < a[i + 1]) break; } ans += (mint)m * (res - prev); prev = res; } print(ans * 2); }