The economy of Syrjälä is booming and industries over all the sectors are growing at breakneck speeds. To move all the raw resources and consumer goods in and out of Syrjälä, new trains arrive every day. Uolevi is in charge of managing Syrjälä's train terminal. He knows the upcoming schedule for n days. On the i-th day a new train begins it's operation and arrives every a_i days to the terminal. Help Uolevi find the number of rails the terminal needs for housing all the trains that arrive on the i-th day.

Input

The first line contains a single integer n. The second line contains n integers a_1,\,a_2,\ldots,\,a_n.

Output

For each of the days 1,2,\dots,n print the number of trains that arrive to the terminal during that day. Print the answers on a single line with space as follows:

\mathrm{ans}_1\quad\mathrm{ans}_2\quad\ldots\quad\mathrm{ans}_n

Constraints

• 1 \leq n \leq 10^5
• 1 \leq a_i \leq n

Example 1

Input:

5
2 3 3 3 1

Output:

1 1 2 1 3

Example 2

Input:

10
10 8 10 1 2 4 10 2 3 1

Output:

1 1 1 1 2 2 3 2 3 5