El proyecto inmobiliario más nuevo en la capital se compone de ~N~ bloques de torres construidos lado a lado a lo largo de un bulevar central y numerados de ~1~ a ~N~. Por cada torre, sabemos la cantidad de pisos de los que está compuesta y más se sabe que no hay dos torres con el mismo número de pisos. Las últimas reglas urbanísticas definen.

El factor de belleza de la torre con el número ~T~ como el número de torres en la secuencia de torres que comienza con la torre ~S~ termina con la torre ~D~ y tiene las siguientes propiedades:

• ~1 \le S \le T \le D \le N~

• el número de pisos de cada torre en la secuencia, excepto la torre ~T~, es menor que el número de pisos de la torre ~T~;

• Si \(S ≠ 1\), la torre ~S-1~ es la torre más cercana a la izquierda de la torre ~T~, que tiene varios pisos estrictamente más grandes que la torre ~T~;

• Si \(D ≠ N\), la torre ~D + 1~ es la torre más cercana a la derecha de la torre ~T~, que tiene una cantidad de pisos estrictamente más grande que la torre ~T~;

El coeficiente de belleza de todo el conjunto de torres es la suma de los coeficientes de belleza de las torres. El desarrollador del proyecto quiere abandonar una de las torres y construir un restaurante subterráneo en su lugar, considerado una torre con cero pisos. El desarrollador desea calcular el coeficiente de belleza de las torres, para cada posible ubicación del restaurante.

Tarea

Al conocer el número ~N~ de torres y el número de piso de cada una, determine el coeficiente de belleza del conjunto de las torres para todas las posibilidades de anidamiento del restaurante ~N~, en la ~1, 2, ..., N~.

Entrada

Los datos de entrada tiene la siguiente estructura:

• la primera línea es el número natural ~N~, que representa el número de torres;

• En la segunda línea hay ~N~ valores naturales, separadas por un espacio, que representan el número de pisos de la torre;

Salida

Los datos de salida se escribirán, en líneas separadas, de modo que: en la línea ~i~ ~(1 \le i \le N)~ hay un número natural que representa el coeficiente de belleza del conjunto si se construye el restaurante en lugar de la torre ~i~.

Restricciones y aclaraciones:

• ~1 \le N \le 100 000~

• El número de pisos de una torre es un número natural entre ~1~ y ~1,000,000,000~.

• Para pruebas de ~30~ puntos, tenemos ~N \le 100~.

• Para pruebas que valen otros ~30~ puntos, tenemos ~N \le 2000~

Ejemplo de Entrada

7
10 3 1 7 8 6 5

Ejemplo de Salida

19
22
22
22
21
22
22

Explicación:

El factor belleza del conjunto es:

La figura 1 es la representación gráfica del archivo de entrada.

Si el restaurante está construido en lugar de la torre 1 (ver figura 2), tenemos los siguientes coeficientes de belleza:

El restaurante tiene el coeficiente 1 (sí mismo).

La torre 2 tiene un coeficiente de 3 (la secuencia compuesta de torres 1,2 y 3)

La torre 3 tiene el coeficiente 1 (sí mismo)

La torre 4 tiene un coeficiente de 4 (la secuencia compuesta de torres 1,2, 3 y 4)

La torre 5 tiene el coeficiente 7 (la secuencia compuesta por todas las torres)

La torre 6 tiene un coeficiente de 2 (la secuencia compuesta por las torres 6 y 7)

La torre 7 tiene el coeficiente 1 (sí mismo)