En la cultura pop y geek existen muchos tipos de energía y poderes ficticios (Ki, Chakra, Haki, Mana, Nen, Cosmos, elixir, el amor, etc.). El gato Milaneso es muy fan de las series y películas de este estilo. Inspirado por ellas, creó un poder ficticio al que llamó MICHI POWER.

Milaneso te asigna n puntos con coordenadas enteras x₁, x₂, …, xₙ en una recta numérica. Para un entero s, se construyen los segmentos [s, x₁], [s, x₂], …, [s, xₙ]. Si xᵢ < s, el segmento se interpreta como [xᵢ, s]. Un segmento [a, b] cubre todos los puntos enteros a, a+1, …, b, incluidos sus extremos.

El MICHI POWER de un punto entero p, denotado por fₚ, es la cantidad de segmentos que contienen el punto p. Para cada elección s = xᵢ, calcula la suma f₁ + f₂ + … + f109 (es decir, desde p = 1 hasta p = 109).

Por ejemplo, para las coordenadas [1, 2, 5, 7, 1] y s = 5, los segmentos son [1,5], [2,5], [5,5], [5,7], [1,5]; la suma de los MICHI POWER es 18.

La primera línea contiene un entero n (1 ≤ n ≤ 2 · 105). La segunda línea contiene n enteros x₁, x₂, …, xₙ (1 ≤ xᵢ ≤ 109).

Imprime n enteros separados por espacios, donde el i-ésimo es la suma pedida para s = xᵢ.