AT_arc158_e [ARC158E] All Pair Shortest Paths

有一个 $2$ 行 $N$ 列的网格。我们用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。在 $(i,j)$ 这个格子上写有正整数 $x_{i,j}$。 如果两个格子有公共边，则称它们**相邻**。 从格子 $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$ 上所写整数的总和。 对于任意两个格子 $X,\ Y$，记 $f(X,\ Y)$ 为从 $X$ 到 $Y$ 的所有路径中权值的最小值。 请你求出所有格子对 $(X,Y)$ 的 $f(X,\ Y)$ 之和，并对 $998244353$ 取模。

输入以如下格式从标准输入读入： > $N$ $x_{1,1}$ $\ldots$ $x_{1,N}$ $x_{2,1}$ $\ldots$ $x_{2,N}$

输出所有格子对 $(X,Y)$ 的 $f(X,\ Y)$ 之和对 $998244353$ 取模的结果。

## 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq x_{i,j} \leq 10^9$ ## 样例解释 1 需要计算以下 $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$。 由 ChatGPT 4.1 翻译