# 誤解法4: min 側の更新で D に足す量の符号を間違える(a - v) # 区間 add d で ΣD^2 += 2dΣD + d^2·len 。O(N log N) import sys MOD = 998244353 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] = (s2[k] + 2*x*s1[k] + x*x % MOD * ln[k]) % MOD s1[k] = (s1[k] + x*ln[k]) % MOD if k < size: lz[k] = (lz[k] + x) % MOD 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] = (s1[2*k] + s1[2*k+1]) % MOD s2[k] = (s2[2*k] + s2[2*k+1]) % MOD 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, a - v); end = s-1; st = s smin.append((a, st)) ans = (ans + s2[1]) % MOD print(ans) main()