B - Diferencias Alternadas I

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Dada una lista de N enteros positivos diferentes, ordenados crecientemente, se desea calcular la suma de las diferencias alternadas de todos los subconjuntos de dicha lista. La diferencia alternada de un conjunto S consiste en ordenar sus elementos ascendentemente, comenzando por el último, alternadamente se sustraen y se suman los sucesivos números. Por ejemplo, la diferencia alternada del conjunto {2, 7, 9, 10} es 10 – 9 + 7 – 2 = 6.

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)

Input
7 1 2 3 4 5 6 7
Output
448