题目描述

Marvolo正看着刚刚入手的北京市地图，路痴的他表示一脸懵逼。刚刚开完会的两人如释负重，决定在帝都游玩一下放松心情，但是就去哪一直拿不定主意。”接下来去哪？”Marvolo问道。”不如去798吧，那里听说挺好玩的”，Mike满脸向往。”怎么，你也想去那里买一个仿真枪，然后在安检处被查水表吗？”Marvolo戏虐道。”假使这些完全无中生有的东西，你再说一遍，你等于..你也有责任吧……”Mike无语的说。

到达798的两人在广场上发现了N件艺术品，两人决定欣赏一番。每个艺术品都有其审美价值Pi。但是这些艺术品要被安排到新的地方，每隔一段时间就会有员工搬走其中剩余的一件艺术品。二人对此很无奈，他们决定每次欣赏的时候都要从剩余的艺术品中挑出连续一段艺术品来欣赏，获得的美感为这一段艺术品的审美价值之和。我们认为一个位置上的艺术品如果被搬走后，其审美价值为负无穷大。现在两人想知道，每次搬走一件艺术品后，他们能获得的美感最大是多少。

输入格式

第一行一个数$N$，表示有$N$个艺术品。

第二行有$N$个整数，表示每个艺术品的审美价值。

第三行有$1 \dots N$共$N$个整数，表示每次搬走的艺术品编号。

输出格式

输出只有一行，一个整数，表示$ans~\mathrm{mod}~998244353$（$=7 \times 17 \times 2^{23}+1$，一个质数），其中$ans$的定义如下：

我们记第$i$次搬走后，获得的美感最大值为$x[i]$，那么

$$ans = \sum_{i=1}^{N}i^2x[i]$$

样例输入

ex_art1.in

4
1 3 2 5
3 4 1 2

样例输出

ex_art1.ans

48

样例解释

搬走第三件艺术品后，剩余审美价值的序列为$1,3，-\inf，5$。则获得美感最大为5。搬走第四件后，为$1,3，-\inf，-\inf$。最大美感为$1+3=4$。由此类推，在最后搬完所有艺术品后，可以选择不看，美感为0。

所以$ans=5 \times 1^2 + 4 \times 2^2 + 3 \times 3^2 + 0 \times 4^2=48$，输出$48~\mathrm{mod}~998244353=48$。

数据范围

对于$20\%$的数据，$1 \leq n,p_{i} \leq 10$

对于$40\%$的数据，$1 \leq n \leq 10^{2}$，$1 \leq p_{i} \leq 10^{3}$

对于$60\%$的数据，$1 \leq n \leq 5 * 10^{3}$，$1 \leq p_{i} \leq 10^{6}$

对于$80\%$的数据，$1 \leq n \leq 10^{5}$，$1 \leq p_{i} \leq 10^{7}$

对于$90\%$的数据，$1 \leq n \leq 10^{6}$

对于$100\%$的数据，$1 \leq n \leq 4 \times 10^{6}$，$1 \leq p_{i} \leq 10^{9}$

时间限制：1s

空间限制：256M

样例数据下载