配点 : $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
3
5

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
1 2
3 4

76

5
1 1000000000 1 1 1
1 1 1 1000000000 1

66714886