Non-equal Neighbours (Codeforces 1591F)
Tags: Math, combinatorics

You are given an array of $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$. Your task is to calculate the number of arrays of $$$n$$$ positive integers $$$b_1, b_2, \ldots, b_n$$$ such that:   $$$1 \le b_i \le a_i$$$ for every $$$i$$$ ($$$1 \le i \le n$$$), and  $$$b_i \neq b_{i+1}$$$ for every $$$i$$$ ($$$1 \le i \le n - 1$$$). The number of such arrays can be very large, so print it modulo $$$998\,244\,353$$$.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Output: Print the answer modulo $$$998\,244\,353$$$ in a single line.

Note: In the first test case possible arrays are $$$[1, 2, 1]$$$ and $$$[2, 1, 2]$$$.In the second test case possible arrays are $$$[1, 2]$$$, $$$[1, 3]$$$, $$$[2, 1]$$$ and $$$[2, 3]$$$.

Sample Inputs:
3
2 2 2

2
2 3

3
1 1 1

Sample Outputs:
2

4

0

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
mod = 998244353
stack = [(0, 0), (a[0], 1)]
now = a[0]
for v in a[1:]:
    to = -now
    now *= 1 - v
    now %= mod
    while stack[-1][0] > v:
        (r, d) = stack.pop()
        now -= (r - v) * d
        now %= mod
        to += d
    stack.append((v, to % mod))
print(now % mod) if n % 2 else print((mod - now) % mod)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
mod = 998244353
stack = [(0, 0), (a[0], 1)]
now = a[0]
for v in a[1:]:
    to = -now
    now *= 1 - v
    now %= mod
    while stack[-1][0] > v:
        (r, d) = stack.pop()
        now -= (r - v) * d
        now %= mod
        to += d
    stack.append((v, to % mod))
if n % 2 == 1:
    print(now % mod)
else:
    print((mod - now) % mod)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
mod = 998244353
stack = [(0, 0), (a[0], 1)]
now = a[0]
for v in a[1:]:
    to = -now
    now *= 1 - v
    now %= mod
    while stack[-1][0] > v:
        (r, d) = stack.pop()
        now -= (r - v) * d
        now %= mod
        to += d
    stack.append((v, to % mod))
print(now % mod) if n % 2 else print((mod - now) % mod)