Hàng xóm khác nhau

Cho mảng gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$. Hãy đếm số mảng $b_1,b_2,\dots ,b_n$ gồm $n$ số nguyên dương thoả mãn đồng thời hai điều kiện:

• $1\le b_i\le a_i$ với mọi $1\le i\le n$;
• $b_i\ne b_{i+1}$ với mọi $1\le i\le n-1$.

Vì kết quả có thể rất lớn, hãy in ra số dư của nó khi chia cho $998244353$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$ — độ dài mảng.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất là đáp án theo modulo $998244353$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le a_i\le {10}^9$

Ví dụ