F. Неравные соседи
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$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$$$.

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Во второй строке задано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Выходные данные

В единственной строке выведите ответ по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
3
2 2 2
Выходные данные
2
Входные данные
2
2 3
Выходные данные
4
Входные данные
3
1 1 1
Выходные данные
0
Примечание

В первом примере подходят массивы $$$[1, 2, 1]$$$ и $$$[2, 1, 2]$$$.

Во втором примере допустимы массивы $$$[1, 2]$$$, $$$[1, 3]$$$, $$$[2, 1]$$$ и $$$[2, 3]$$$.