CF1591F Non-equal Neighbours

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 $ .

N/A

N/A

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] $ .