/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
2 行 N 列のマス目があります．上から i 行目，左から j 列目のマスを (i,j) で表します．(i,j) には正整数 x_{i,j} が書かれています．
2 つのマスは，辺を共有するときに隣接するといいます．
マス X から Y へのパスとは，相異なるマスからなる列 (P_1, \ldots, P_n) であって，P_1 = X, P_n = Y であり，任意の 1\leq i \leq n-1 に対して P_i と P_{i+1} が隣接するものをいいます．さらに，そのパスの重みを P_1, \ldots, P_n に書かれている整数の総和として定義します．
2 つのマス X, Y に対して，X から Y へのパスの重みとしてありうる最小値を f(X, Y) と書くことにします．すべてのマスの 2 つ組 (X,Y) に対する f(X, Y) の総和を 998244353 で割った余りを求めてください．
制約
- 1\leq N\leq 2\times 10^5
- 1\leq x_{i,j} \leq 10^9
入力
入力は以下の形式で標準入力から与えられます．
N
x_{1,1} \ldots x_{1,N}
x_{2,1} \ldots x_{2,N}
出力
すべてのマスの 2 つ組 (X,Y) に対する f(X, Y) の総和を 998244353 で割った余りを出力してください．
入力例 1
1 3 5
出力例 1
24
次の 4 通りの値の総和を求めます．
- X = (1,1), Y = (1,1) のとき：f(X, Y) = 3．
- X = (1,1), Y = (2,1) のとき：f(X, Y) = 8．
- X = (2,1), Y = (1,1) のとき：f(X, Y) = 8．
- X = (2,1), Y = (2,1) のとき：f(X, Y) = 5．
入力例 2
2 1 2 3 4
出力例 2
76
入力例 3
5 1 1000000000 1 1 1 1 1 1 1000000000 1
出力例 3
66714886
Score : 800 points
Problem Statement
We have a grid with 2 rows and N columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left. (i,j) has a postive integer x_{i,j} written on it.
Two squares are said to be adjacent when they share a side.
A path from square X to Y is a sequence (P_1, \ldots, P_n) of distinct squares such that P_1 = X, P_n = Y, and P_i and P_{i+1} are adjacent for every 1\leq i \leq n-1. Additionally, the weight of that path is the sum of integers written on P_1, \ldots, P_n.
For two squares X and Y, let f(X, Y) denote the minimum weight of a path from X to Y. Find the sum of f(X, Y) over all pairs of squares (X,Y), modulo 998244353.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq x_{i,j} \leq 10^9
Input
The input is given from Standard Input in the following format:
N
x_{1,1} \ldots x_{1,N}
x_{2,1} \ldots x_{2,N}
Output
Print the sum of f(X, Y) over all pairs of squares (X,Y), modulo 998244353.
Sample Input 1
1 3 5
Sample Output 1
24
You should find the sum of the following four values.
- For X = (1,1), Y = (1,1): f(X, Y) = 3.
- For X = (1,1), Y = (2,1): f(X, Y) = 8.
- For X = (2,1), Y = (1,1): f(X, Y) = 8.
- For X = (2,1), Y = (2,1): f(X, Y) = 5.
Sample Input 2
2 1 2 3 4
Sample Output 2
76
Sample Input 3
5 1 1000000000 1 1 1 1 1 1 1000000000 1
Sample Output 3
66714886