版权声明

本题版权归 Long Long OJ 所有。

题目描述

小 A 建了一个有 $n$ 个房间的圆形羊房，每个房间按顺时针从 $1$ 到 $n$ 进行编号，编号为 $n$ 的的房间与编号为 $1$ 的房间相邻，相邻的两个房间有通道相连，每个房间都有个向外开的门。

小 A 想用这些房间养羊，第 $i$ 个房间养 $r_i$ 头羊。为了把这些羊有序地赶进房间，他计划把一个房间连向外面的门打开，使得所有的羊都从这扇门进入。

这些羊进入房间后沿顺时针方向穿过这些房间，直到羊到达自己的房间。小 A 想使得所有的羊走过的总距离最短。请你帮小 A 确定所有的羊从哪个房间进入，使得羊走的总路程最短，求最短的路程。每头羊走过的路程为它经过的房间的数目。

输入格式

第一行仅一个整数 $n$。

接下来的一行表示 $r_i$，意思是第 $i$ 个房间住 $r_i$ 头羊，以空格隔开。

输出格式

输出仅一个数，即羊走过距离总和的最小值 $(\bmod\ 998244353)$。

样例

5
4 7 8 6 4

48

提示

样例解释：

共 $5$ 个房间，第 $1$ 个房间 $4$ 头羊，第 $2$ 个房间 $7$ 头羊，第 $3$ 个房间 $8$ 头羊，第 $4$ 个房间 $6$ 头羊，第 $5$ 个房间 $4$ 头羊。

最好的方式是打开第 $2$ 个房间的门，让所有的羊从第 $2$ 个房间进入。这样，有 $7$ 只羊不用走（第 $2$ 个房间），有 $8$ 只羊走到第 $3$ 个房间，路程为 $1\times8=8$；有 $6$ 只羊走到第 $4$ 个房间，路程为 $2\times 6=12$ ；有 $4$ 只羊走到第 $5$ 个房间，路程为 $3\times4=12$；有 $4$ 只羊走到第 $1$ 个房间，路程为 $4\times4=16$；$8+12+12+16=48$。

对于 $10\%$ 的数据，$1 \leq n \leq 10,1 \leq r_i \leq 10$；

对于 $20\%$ 的数据，$1 \leq n \leq 10^2,1 \leq r_i \leq 10^2$；

对于 $30\%$ 的数据，$1 \leq n \leq 10^3,1 \leq r_i \leq 10^2$；

对于 $40\%$ 的数据，$1 \leq n \leq 10^5,1 \leq r_i \leq 10^3$。

对于 $50\%$ 的数据，$1 \leq n \leq 10^6,1 \leq r_i \leq 10^5$。

对于 $60\%$ 的数据，$1 \leq n \leq 2\times10^6,1 \leq r_i \leq 2\times10^5$。

对于 $80\%$ 的数据，$1 \leq n \leq 3\times10^6,1 \leq r_i \leq 2\times10^5$。

对于 $100\%$ 的数据，$1 \leq n \leq 5\times10^6,1 \leq r_i \leq 2\times10^5$。