P6170 [USACO16FEB] Circular Barn G

*This problem has the same meaning as the [Silver problem with the same name](/problem/P3137). The only difference is the Constraints.*

As a fan of modern architecture, Farmer John built a new circular barn. Inside the barn there are $n$ rooms arranged in a ring ($3 \leq n \leq 10^5$), numbered $1 \ldots n$ in clockwise order. Each room has doors to its left and right neighboring rooms, and also a door leading outside. Now FJ has $n$ cows, and his goal is to have exactly one cow in each room. Unfortunately, the cows are currently in random rooms: room $i$ contains $c_i$ cows. It is guaranteed that $\sum c_i = n$. FJ decides to solve this problem as follows: he will have some cows move **clockwise**, passing through some rooms to reach their assigned positions. If a cow passes through $d$ doors, the energy it uses is $d^2$. You need to help FJ compute the minimum possible total energy used by all cows.

The first line contains an integer $n$. The next $n$ lines each contain an integer $c_i$ on line $i$.

Output the minimum total energy used by all cows.

Translated by ChatGPT 5