Byteasar tiene una casa de campo. Últimamente, él ha comprado ~n~ árboles y los ha sembrado a todos en una fila. Sin embargo, a Byteasar no le ha gustado el orden en el cual los árboles han sido plantados. El está particularmente molesto ya que árboles grandes y pequeños están mezclados y a esta composición no le encuentra su criterio estético.

Byteasar ha inventado un coeficiente de desorden que le permita al jardinero comprender sus intensiones: a un valor más pequeño del coeficiente más hermosa es la hilera de árboles. Está definido de la siguiente manera: ~|h_1-h_2|+|h_2-h_3|+...+|h_{n-1} -h_n|~, donde ~h_1, h_2, . . . ,h_n~ están las alturas de árboles consecutivos en una fila.

Replantar es una tarea muy embarazosa, por lo tanto Byteasar ha orientado al jardinero replantar dos árboles a lo sumo (es decir intercambiar sus posiciones). La tarea del jardinero es elegir los pares a replantar de una manera que el coeficiente de desorden sea el más pequeño. El jardinero no está seguro si el ha elegido el par correcto de árboles y teme que pueda perder su trabajo si se equivoca. Ayúdelo: para cada árbol calcule el coeficiente de desorden mínimo que el puede alcanzar intercambiando lugares con cualquier otro árbol.

Escriba un programa el cual:

• Lea desde la entrada estándar la altura de los árboles consecutivos en una línea.

• Para cada árbol calcule el coeficiente de desorden mínimo que puede ser alcanzado debido al intercambio de lugares con algún otro árbol (o no debe haber cambio de ninguna manera),

• Escriba el resultado para la salida estándar.

Entrada

La primera línea de la entrada estándar contiene un entero ~n (2 \leq n \leq 50000)~. Las otras contienen ~n~ enteros ~h_i (1 \leq h_i \leq 100000000)~ separados por espacios simples, denotando la altura de los árboles consecutivos en la fila.

Salida

La salida debe consistir precisamente de ~n~ líneas. La i-th línea debe contener un entero simple - el coeficiente de desorden más pequeño alcanzable cuando consideramos reemplazar el i-ésimo árbol.

Ejemplo #1 de Entrada

5
7 4 5 2 5

Ejemplo #1 de Salida

7
7
8
7
7

Ejemplo #2 de Entrada

5
1 2 3 4 5

Ejemplo #2 de Salida

4
4
4
4
4

En el primer ejemplo un valor de ~7~ del coeficiente de desorden puede ser alcanzado reemplazando el árbol ~1~ y ~4~, ~2~ y ~5~ ó ~4~ y ~5~. Así, reemplazando cualquiera de los árboles anteriormente mencionados ~(1,2,4,5)~ y su homólogo un coeficiente de desorden de valor ~7~ puede ser obtenido. Solamente para el árbol ~3~ el mejor resultado posible es el más grande - este es ~8~. En el segundo ejemplo cualquier reemplazo incrementa el valor del coeficiente de desorden, así que ningún cambio debe tener lugar; todos los coeficientes de desorden tienen el valor inicial ~(4)~.