Олимпиадный тренинг

Задача . Разности


Задача

Темы:

У Джона Доу есть массив a из n элементов. Джон хочет найти величину , то есть сумму квадратов разностей элементов массива по всем возможным парам i, j.

Например для массива {1, 2, 3} такая величина будет равна (1 - 1)2 + (1 - 2)2 + (1 - 3)2 + (2 - 1)2 + (2 - 2)2 + (2 - 3)2 + (3 - 1)2 + (3 - 2)2 + (3 - 3)2 = 0 + 1 + 4 + 1 + 0 + 1 + 4 + 1 + 0 = 12

Найдите остаток от деления S на 108.

Напомним, как работать с остатками от деления. Остаток от деления числа a на число b обозначим как . Верны следующие соотношения:

  • (для a ≥ b).

 

К примеру, вы хотите посчитать величину . Перемножить эти три числа в стандартном типе данных вам не удастся, но можно воспользоваться первым соотношением и посчитать сначала Теперь можно перемножить получившееся число и 107 + 3 и получить .

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 106) — количество элементов массива. Во второй строке через пробел записаны n целых чисел a1, ..., an (1 ≤ ai ≤ 109).

Выходные данные

Выведите остаток от деления S на 108.

Примеры тестов

Входные данные

3
1 2 3
Выходные данные
12
Входные данные
5
100 1 9 1 3
Выходные данные
74928
Входные данные
2
1000000000 1
Выходные данные
2

Примечание

Тесты поделены на несколько групп, но оцениваются отдельно.

  • n, ai ≤ 1000 – 10 баллов
  • n ≤ 5000 – 10 баллов
  • n ≤ 106 ai ≤ 5000 – 30 баллов
  • Без дополнительных ограничений — 50 баллов

Например, если вы решили задачу для n ≤ 5000 и произвольных ai вы получите 20 баллов (первая и вторая группы).



time 1000 ms
memory 64 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w642
Комментарий учителя