版权声明

本题版权归 Long Long OJ 所有。

题目描述

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

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

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

答案对 $998244353$ 取模。

输入格式

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

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

输出格式

输出仅一个数，即羊走过距离总和的最小值。

答案对 $998244353$ 取模。

样例

5
4 7 8 6 4

48

样例解释

共 $5$ 个房间：

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

最好的方式是打开第 $2$ 个房间的门，让所有的羊从第 $2$ 个房间进入，这样:

• 有 $7$ 只羊不用走，路程为 $0$。
• 有 $8$ 只羊走到第 $3$ 个房间，路程为 $1\times8=8$。
• 有 $6$ 只羊走到第 $4$ 个房间，路程为 $2\times6=12$。
• 有 $4$ 只羊走到第 $5$ 个房间，路程为 $3\times4=12$。
• 有 $4$ 只羊走到第 $1$ 个房间，路程为 $4\times4=16$。

总用时为 $8+12+12+16=48$。

数据范围

• 对于 $10\%$ 的数据，$1 \le n \le 10$，$1 \le r_i \le 10$。
• 对于 $20\%$ 的数据，$1 \le n \le 10^2$，$1 \le r_i \le 10^2$。
• 对于 $30\%$ 的数据，$1 \le n \le 10^3$，$1 \le r_i \le 10^2$。
• 对于 $40\%$ 的数据，$1 \le n \le 10^5$，$1 \le r_i \le 10^3$。
• 对于 $50\%$ 的数据，$1 \le n \le 10^6$，$1 \le r_i \le 10^5$。
• 对于 $60\%$ 的数据，$1 \le n \le 2 \times 10^6$，$1 \le r_i \le 2 \times 10^5$。
• 对于 $80\%$ 的数据，$1 \le n \le 3 \times 10^6$，$1 \le r_i \le 2 \times 10^5$。
• 对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^6$，$1 \le r_i \le 2 \times 10^5$。