Siendo admirador de la arquitectura contemporánea, el Granjero Juan ha construido un nuevo establo con la forma de un círculo perfecto. En su interior, el establo consiste de un anillo de ~N~ habitaciones, numeradas en sentido horario ~1~ . . . ~N~ alrededor del perímetro del establo ~(3 \leq N \leq 1,000)~. Cada habitación tiene puertas a sus dos habitaciones vecinas y también una puerta al exterior del establo. El Granjero Juan quiere que exactamente ~r_i~ vacas terminen en cada habitación ~i~ ~(1 \leq r_i \leq 100)~. Para arrear a las vacas dentro del establo de una manera ordenada, él planea abrir la puerta exterior de una sola habitación, permitiendo que las vacas entren a través de esa puerta. Cada vaca entonces camina en orden horario a través de las habitaciones hasta que ella encuentra un destino apropiado.

El Granjero Juan quiere abrir la puerta exterior que causará que las vacas caminen colectivamente la cantidad mínima de distancia. Por favor, determine la cantidad mínima que las vacas necesitan caminar, si él elije la mejor de esas puertas para abrirla. La distancia caminada por una sola vaca es el número de puertas interiores a través de las cuales ella pasa.

Entrada

La primera línea de la entrada contiene ~N~.

Cada una de las ~N~ líneas restantes contiene ~r_1,r_2~ ~. . .r_N~

Salida

Escriba, por favor, la cantidad mínima total de la distancia que las vacas necesitan recorrer colectivamente.

Ejemplo de Entrada

5
4
7
8
6
4

Ejemplo de Salida

48

En este ejemplo, la mejor solución es dejar que las vacas entren a través de la puerta de la habitación que requiere 7 vacas.