Вывод формулы

У Джона Доу есть массив 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 на 10⁸.

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

• 
• 
• (для a ≥ b).

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

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

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

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

3
1 2 3

12

5
100 1 9 1 3

74928

2
1000000000 1

2

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

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

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

Текст программы p141.pas

const nmax=100;

var a:array[1..nmax] of integer;
    n:integer;
    i,j,g:integer;

    f1,f2:text;

begin
assign(f1,'input.txt');
reset(f1);
assign(f2,'output.txt');
rewrite(f2);
                                  {Чтение входных данных}
read(f1,n);
for i:=1 to n do read(f1,a[i]);
                                  {Сортировка массива}

for i:=1 to n do begin            {Подбираем число на i-ое место}

  g:=i;                           {Считаем, что самое маленькое число,
                                   которое нам встретилось, стоит на месте i}

  for j:=i+1 to n do              {Перебираем все числа с i+1 до конца массива}
    if a[j]<a[g] then g:=j;       {Если нашли число, которое меньше,
                                   чем то, что уже найдено, запоминаем его}

                                  {Меняем местами числа, стоящие на i-ом и
                                   на g-ом местах }
                                  {Если a[i]=x, a[g]=y, то после выполнения
                                   команды: }
  if i<>g then begin
    a[i]:=a[i]+a[g];                {a[i]=x+y, a[g]=y}
    a[g]:=a[i]-a[g];                {a[i]=x+y, a[g]=(x+y)-y=x}
    a[i]:=a[i]-a[g];                {a[i]=(x+y)-x=y}
                                  {То есть после этого a[i]=y, a[g]=x
                                   обмен значений произошел}
    end;

  end;

                                  {Выводим результат}
for i:=1 to n do
  write(f2,a[i],' ');
close(f1);
close(f2);
end.