# 誤解法3: 途中で mod を取らず long long で計算し、最後に一度だけ mod(int64 オーバーフロー) # Python では W() で C++ の 64bit 符号付き整数の wrap を再現している import sys MOD = 998244353 def W(x): return ((x + (1 << 63)) & ((1 << 64) - 1)) - (1 << 63) def cmod(x): # C++ の % (0方向切り捨て) return x % MOD if x >= 0 else -((-x) % MOD) def main(): d = sys.stdin.read().split() n = int(d[0]); A = list(map(int, d[1:1+n])) size = 1 while size < n: size *= 2 s1 = [0]*(2*size); s2 = [0]*(2*size); ln = [0]*(2*size); lz = [0]*size for i in range(size): ln[size+i] = 1 for i in range(size-1, 0, -1): ln[i] = ln[2*i] + ln[2*i+1] def ap(k, x): s2[k] = W(s2[k] + W(W(2*x)*s1[k]) + W(W(x*x)*ln[k])) s1[k] = W(s1[k] + W(x*ln[k])) if k < size: lz[k] = W(lz[k] + x) def push(k): if lz[k]: ap(2*k, lz[k]); ap(2*k+1, lz[k]); lz[k] = 0 def pull(k): s1[k] = W(s1[2*k] + s1[2*k+1]) s2[k] = W(s2[2*k] + s2[2*k+1]) LOG = size.bit_length() - 1 def add(l, r, x): # [l, r) if l >= r: return l += size; r += size for i in range(LOG, 0, -1): if ((l >> i) << i) != l: push(l >> i) if ((r >> i) << i) != r: push((r-1) >> i) l2, r2 = l, r while l2 < r2: if l2 & 1: ap(l2, x); l2 += 1 if r2 & 1: r2 -= 1; ap(r2, x) l2 >>= 1; r2 >>= 1 for i in range(1, LOG+1): if ((l >> i) << i) != l: pull(l >> i) if ((r >> i) << i) != r: pull((r-1) >> i) smax = []; smin = []; ans = 0 for r in range(n): a = A[r] end = r-1; st = r while smax and smax[-1][0] <= a: v, s = smax.pop(); add(s, end+1, a - v); end = s-1; st = s smax.append((a, st)) end = r-1; st = r while smin and smin[-1][0] >= a: v, s = smin.pop(); add(s, end+1, v - a); end = s-1; st = s smin.append((a, st)) ans = W(ans + s2[1]) print(cmod(ans)) main()