## USACO 2016 February Contest, Silver

## Problem 1. Circular Barn

Contest has ended.

**Log in to allow submissions in analysis mode**

Farmer John owns $n$ cows, and he wants exactly one cow to end up in each room in the barn. However, the cows, being slightly confused, line up at haphazard doors, with possibly multiple cows lining up at the same door. Precisely $c_i$ cows line up outside the door to room $i$, so $\sum c_i = n$.

To manage the process of herding the cows so that one cow ends up in each room, Farmer John wants to use the following approach: each cow enters at the door at which she initially lined up, then walks clockwise through the rooms until she reaches a suitable destination. Given that a cow walking through $d$ doors consumes $d^2$ energy, please determine the minimum amount of energy needed to distribute the cows so one ends up in each room.

#### INPUT FORMAT (file cbarn.in):

The first line of input contains $n$. Each of the remaining $n$ lines contain $c_1 \ldots c_n$.#### OUTPUT FORMAT (file cbarn.out):

Please write out the minimum amount of energy consumed by the cows.#### SAMPLE INPUT:

10 1 0 0 2 0 0 1 2 2 2

#### SAMPLE OUTPUT:

33

Problem credits: Brian Dean