A - Subarray Sum

Languages: C, C++, Java, Python, C#
Time & Memory limits: (details)

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: 

$\begin{equation*} G(b) = \max_{ 0\leq i \leq j < length(b) } |b_i - b_j|^{2} \end {equation*}$

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)

Input
5 1 2 3 4 5
Output
50