D.E. shaw Online assessment (summer intern '26)

Given a binary string s of length n (each character is '0' or '1').

Find the number of ways to pick three indices i < j < k such that:

s[i] != s[j] (no two adjacent picks have the same value)

s[j] != s[k]

constraint : n <=2 * 10 ^ 5

You have n groups of tasks in a line. Each group i has tasks[i] tasks.

You can do the following operation any number of times:

Choose a group i (1 ≤ i ≤ n):

If i > 1, move 1 task from group i to group i-1.

This changes: tasks[i] -= 1 tasks[i-1] += 1 If i < n, move 1 task from group i to group i+1.

This changes: tasks[i] -= 1 tasks[i+1] += 1 Each such move costs 1.

return the minimum number of moves required to make array non-increasing.

constaint : n <= 250

You are given an array a of length n. Each a[i] represents the time complexity allowed at position i.

Your task is to count the number of valid arrays b of length n satisfying:

For each position i (1 ≤ i ≤ n), 1 ≤ b[i] ≤ a[i].

No two consecutive elements are equal, i.e. b[i] ≠ b[i+1] for all 1 ≤ i < n.

Since the answer may be large, print it modulo 998244353.

Input The first line contains a single integer n (1 ≤ n ≤ 2⋅10^5), the length of the array.

The second line contains n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^9).

Output Print a single integer — the number of valid arrays b modulo 998244353