Matcom Online Grader

Fito tiene en su poder un arreglo de $n$ elementos, $a= [ a_0, a_1, .... , a_{n-1}]$. Para un subarray $b$, de $a$, se define $G(b)$ como: 

donde $length(b)$ es la longitud de $b$, y $b_i$ es el i-ésimo elemento de $b$.

Él desea calcular la suma de $G(b)$ para todo posible subarreglo $b$ de $a$ computando:

$\begin{equation*} \sum_{ 0\leq l \leq r < n } G(a_{l \dots r}) \end {equation*}$

donde $a_{l \dots r}$ es el subarreglo de $a$ del índice $l$ al $r$.

Dado $a$ imprima la suma módulo $2^{64}$.

Input

La primera línea tendrá un entero $n$ (el tamaño del arreglo $a$).

La segunda línea contiene $n$ enteros separados por espacio descibiendo los valores respectivos de $a_0, a_1, .... , a_{n-1}$.

Restricciones:

• $1 \leq n \leq 2 \ast 10^{5}$
  
• $1 \leq a_i \leq 2 \ast 10^{5}$
  

Output

Imprima un entero que denote la suma requerida módulo $2^{64}$.

Sample test(s)