E - LEQ and NEQ Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ N の整数列 A_1,A_2,\ldots,A_N が与えられます。長さ N の整数列 X_1,X_2,\ldots,X_N であって、以下の条件をすべて満たすものはいくつあるか求め、998244353 で割った余りを出力してください。

  • 1 \leq X_i \leq A_i
  • X_i \neq X_{i+1} (1 \leq i \leq N-1)

制約

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
2 3 2

出力例 1

6

条件をすべて満たす整数列は以下の 6 通りです。

  • 1,2,1
  • 1,3,1
  • 1,3,2
  • 2,1,2
  • 2,3,1
  • 2,3,2

入力例 2

10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

出力例 2

524691026

Score : 700 points

Problem Statement

Given is a sequence of N integers A_1,A_2,\ldots,A_N. Print the number, modulo 998244353, of sequences of N integers X_1,X_2,\ldots,X_N satisfying all of the following conditions:

  • 1 \leq X_i \leq A_i
  • X_i \neq X_{i+1} (1 \leq i \leq N-1)

Constraints

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

3
2 3 2

Sample Output 1

6

The following six sequences satisfy all of the conditions.

  • 1,2,1
  • 1,3,1
  • 1,3,2
  • 2,1,2
  • 2,3,1
  • 2,3,2

Sample Input 2

10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

Sample Output 2

524691026