/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
長さ N の数列 A が与えられます。
A を空でない、連続した部分列 B_1,B_2,\ldots,B_k に切り分ける方法は 2^{N-1} 通りありますが、そのすべてについて以下の値を求め、総和を 998244353 で割ったあまりを出力してください。
- \prod_{i=1}^{k} (\max(B_i)-\min(B_i))
ここである数列 B_i=(B_{i,1},B_{i,2},\ldots,B_{i,j}) について、\max(B_i) を B_i に含まれる要素の最大値、\min(B_i) を B_i に含まれる要素の最小値と定義します。
制約
- 1 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
求めた値の総和を 998244353 で割ったあまりを出力せよ。
入力例 1
3 1 2 3
出力例 1
2
A=(1,2,3) を空でない連続した部分列に切り分ける方法は以下の 4 通りです。
- (1) と (2) と (3)
- (1) と (2,3)
- (1,2) と (3)
- (1,2,3)
それぞれにおける \prod_{i=1}^{k} (\max(B_i)-\min(B_i)) は順に 0, 0, 0, 2 であるため、その総和である 2 を出力します。
入力例 2
4 1 10 1 10
出力例 2
90
入力例 3
10 699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794
出力例 3
877646588
998244353 で割ったあまりを出力することに注意してください。
Score : 600 points
Problem Statement
Given is a sequence A of N numbers.
There are 2^{N-1} ways to divide A into non-empty contiguous subsequences B_1,B_2,\ldots,B_k. Find the value below for each of those ways, and print the sum, modulo 998244353, of those values.
- \prod_{i=1}^{k} (\max(B_i)-\min(B_i))
Here, for a sequence B_i=(B_{i,1},B_{i,2},\ldots,B_{i,j}), \max(B_i) and \min(B_i) are defined to be the maximum and minimum values of an element of B_i, respectively.
Constraints
- 1 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the sum, modulo 998244353, of the values found.
Sample Input 1
3 1 2 3
Sample Output 1
2
There are 4 ways to divide A=(1,2,3) into non-empty contiguous subsequences, as follows.
- (1), (2), (3)
- (1), (2,3)
- (1,2), (3)
- (1,2,3)
\prod_{i=1}^{k} (\max(B_i)-\min(B_i)) for these divisions are 0, 0, 0, 2, respectively. The sum of them, 2, should be printed.
Sample Input 2
4 1 10 1 10
Sample Output 2
90
Sample Input 3
10 699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794
Sample Output 3
877646588
Be sure to print the sum modulo 998244353.