← 返回题目列表

AtCoder · arc201_e

E. 边界框的总面积

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

有 N 点编号 1,2, \dots, N 上 2维度平面。 点的坐标 i 是 (i,Y_i)。 在这个问题中,可以保证 Y=(Y_1,Y_2,\dots ,Y_N) 是一个排列 (1,2, \dots ,N).

求所有子集的边界框面积之和 S of \lbrace \texttt{point}\,1,\texttt{point}\,2,\dots ,\texttt{point}\,N \rbrace 至少 2 元素,模数 998244353.

的边界框 S 指边平行于矩形的最小面积矩形 x- 包含所有点的轴 S 内部或边界上。

约束

  • 2 \le N \le 2 \times 10^5
  • Y 是一个排列 (1,2, \dots ,N).
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
Y_1 Y_2 \ldots Y_N

输出

输出总和,模数 998244353,边界框的区域。


示例输入 1

4
2 3 1 4

示例输出 1

50

每个子集及其边界框的面积如下图所示。输出面积之和,即 50.


示例输入 2

26
6 14 8 19 13 25 26 22 7 3 16 15 11 24 1 12 20 23 5 17 9 2 21 10 4 18

示例输出 2

575187918