Super sum

Given N integers. Required for each number to find the number of options to split the sum of two other numbers from the set.

Input

The first line contains the number N (1 ≤ N ≤ 10000). Next, set N of natural numbers not exceeding 1000000000. For each number of partitions is less than 2^31.

Output

Print the N numbers (one per line) - the number of partitions in a manner consistent with the original.

Examples