Count Ways to Select Fleet

Two-wheel and four-wheel vehicles are available in unlimited supply. For each total number of wheels, count the distinct combinations of the numbers of the two vehicle types.

输入格式

The first line contains n (1..100000), and the second line contains n wheel totals (1..10⁹).

输出格式

Output n integers in input order.

样例 1

输入：

3
6 3 2

输出：

2 0 1

样例 2

输入：

3
4 5 6

输出：

2 0 2

样例 3

输入：

2
1 8

输出：

0 3

样例说明

Example 1: 6 has the two options (3,0) and (1,1), 3 has no solution, and 2 has only (1,0), so output 2 0 1. Example 2: 4 and 6 have two options each, and 5 has no solution. Example 3: 1 has no solution; 8 has three options with 0, 1 or 2 four-wheelers, so output 0 3.