Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Lea el problema “ Diferencias Alternadas I ”… Calcule la suma de las diferencias alternadas de todos los segmentos de una lista. Sea A una lista de tamaño N, se define un segmento [i, j] como el conjunto de los elementos con índice i, i+1,…, j (con 1 <= i <= j <= N). Usted debe calcular la suma de las diferencias alternadas de todos los segmentos de la lista dada.

Input

Línea 1 : Un único entero N (1 <= N <= 200000).
Línea 2 : N enteros a1 < a2 < … < aN separados por espacio (1 <= ai <= 10^9).

Output

Línea 1 : Su respuesta módulo 987654321.

Sample test(s)