Суперсумма

Дано N натуральных чисел. Требуется для каждого числа найти количество вариантов разбиения его на сумму двух других чисел из данного набора.

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

В первой строке дано число N (1 ≤ N ≤ 10000). Далее заданы N натуральных чисел, не превосходящих 1000000000. Для каждого числа количество разбиений меньше 2^31.

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

Вывести N чисел (по одному в строке) – количество разбиений, в порядке, соответствующем исходному.

Примеры