Вам дан массив \(a_1, a_2, \ldots, a_n\) длины \(n\), состоящий из положительных целых чисел. Ваша задача — посчитать количество массивов целых чисел \(b_1, b_2, \ldots, b_n\) длины \(n\) таких, что:
- \(1 \le b_i \le a_i\) для всех \(i\) (\(1 \le i \le n\)), и
- \(b_i \neq b_{i+1}\) для всех \(i\) (\(1 \le i \le n - 1\)).
Количество таких массивов может быть очень большим, поэтому выведите это число по модулю \(998\,244\,353\).
Выходные данные
В единственной строке выведите ответ по модулю \(998\,244\,353\).
Примечание
В первом примере подходят массивы \([1, 2, 1]\) и \([2, 1, 2]\).
Во втором примере допустимы массивы \([1, 2]\), \([1, 3]\), \([2, 1]\) и \([2, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 2 2
|
2
|
|
2
|
2
2 3
|
4
|
|
3
|
3
1 1 1
|
0
|