E - LEQ and NEQ

Contest Duration: 2021-03-21(Sun) 11:00 - 2021-03-21(Sun) 13:00 (local time) (120 minutes) Back to Home

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$

出力

答えを出力せよ。

入力例 1Copy

Copy

3
2 3 2

出力例 1Copy

Copy

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

$1,2,1$
$1,3,1$
$1,3,2$
$2,1,2$
$2,3,1$
$2,3,2$

入力例 2Copy

Copy

10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

出力例 2Copy

Copy

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 1Copy

Copy

3
2 3 2

Sample Output 1Copy

Copy

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 2Copy

Copy

10
158260522 877914575 602436426 24979445 861648772 623690081 433933447 476190629 262703497 211047202

Sample Output 2Copy

Copy

524691026