Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Description

Little A built a circular sheepfold with $n$ rooms, numbered clockwise from $1$ to $n$. The room numbered $n$ is adjacent to the room numbered $1$, and adjacent rooms are connected by passages. Each room has a door opening outward.

Little A wants to raise sheep in these rooms, with $r_i$ sheep in the $i$-th room. To drive the sheep into the rooms in an orderly manner, he plans to open the outward door of one room so that all sheep enter through this door.

After entering the room, the sheep walk clockwise through the rooms until they reach their own room. Little A wants to minimize the total distance traveled by all sheep. Please help Little A determine which room's door to open for all sheep to enter, such that the total distance traveled by the sheep is minimized, and find this minimum total distance. The distance traveled by each sheep is the number of rooms it passes through.

Input Format

The first line contains only one integer $n$.

The next line contains $r_i$ (separated by spaces), representing the number of sheep in the $i$-th room.

Output Format

Output only one number, which is the minimum value of the total distance traveled by the sheep.

The answer should be taken modulo $998244353$.

Samples

5
4 7 8 6 4

48

Sample 1 Explanation

There are $5$ rooms in total: $4$ sheep in Room $1$, $7$ sheep in Room $2$, $8$ sheep in Room $3$, $6$ sheep in Room $4$, and $4$ sheep in Room $5$.

The optimal way is to open the door of Room $2$ and let all sheep enter through Room $2$. In this case:

• $7$ sheep (in Room $2$) do not need to walk;
• $8$ sheep walk to Room $3$, with a total distance of $1 \times 8 = 8$;
• $6$ sheep walk to Room $4$, with a total distance of $2 \times 6 = 12$;
• $4$ sheep walk to Room $5$, with a total distance of $3 \times 4 = 12$;
• $4$ sheep walk to Room $1$, with a total distance of $4 \times 4 = 16$.

The total distance is $8 + 12 + 12 + 16 = 48$.

Data Range

• For $10\%$ of the data: $1 \le n \le 10, 1 \le r_i \le 10$;
• For $20\%$ of the data: $1 \le n \le 10^2, 1 \le r_i \le 10^2$;
• For $30\%$ of the data: $1 \le n \le 10^3, 1 \le r_i \le 10^2$;
• For $40\%$ of the data: $1 \le n \le 10^5, 1 \le r_i \le 10^3$;
• For $50\%$ of the data: $1 \le n \le 10^6, 1 \le r_i \le 10^5$;
• For $60\%$ of the data: $1 \le n \le 2\times10^6, 1 \le r_i \le 2\times10^5$;
• For $80\%$ of the data: $1 \le n \le 3\times10^6, 1 \le r_i \le 2\times10^5$;
• For $100\%$ of the data: $1 \le n \le 5\times10^6, 1 \le r_i \le 2\times10^5$.