Bài 2

Cho dãy số nguyên $N$ ($1 \le N \le 2 \cdot 10^5$) gồm phần tử $A = (a_1, a_2, \dots, a_n)$. Trọng số $C$ của $A$ được tính như sau:

$C = \sum_{i=1}^{n} i \times a_i$

Được phép thực hiện một lần biến đổi trên dãy $A$ bằng cách di chuyển một phần tử đến vị trí đầu hoặc cuối dãy. Tìm trọng số $C$ lớn nhất thu được.

Số nguyên $N$ và dãy số nguyên $a_1, a_2, \dots, a_n$ ($|a_i| \le 10^6$).

Một số nguyên là trọng số $C$ lớn nhất thu được.

• $1 \le N \le 2 \cdot 10^5$
• $|a_i| \le 10^6$