A. Rooms and Passages
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$(n+1)$$$ rooms in the dungeon, consequently connected by $$$n$$$ passages. The rooms are numbered from $$$0$$$ to $$$n$$$, and the passages — from $$$1$$$ to $$$n$$$. The $$$i$$$-th passage connects rooms $$$(i-1)$$$ and $$$i$$$.

Every passage is equipped with a security device of one of two types. Security device of the first type checks if a person who walks through the passage has the pass of the certain color, and forbids movement if such pass is invalid. Security device of the second type never forbids movement, but the pass of the certain color becomes invalid after the person walks through.

In the beginning you are located in the room $$$s$$$ and have all the passes. For every $$$s$$$ from $$$0$$$ to $$$(n-1)$$$ find how many rooms you can walk through in the direction of the room $$$n$$$.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 500000$$$) — the number of passages.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le |a_i| \le n$$$). The number $$$|a_i|$$$ is a color of the pass which the $$$i$$$-th passage works with. If $$$a_i \gt 0$$$, the $$$i$$$-th passage is the first type passage, and if $$$a_i \lt 0$$$ — the second type.

Output

Output $$$n$$$ integers: answers for every $$$s$$$ from $$$0$$$ to $$$(n-1)$$$.

Examples
Input
6
1 -1 -1 1 -1 1
Output
3 2 1 2 1 1
Input
7
2 -1 -2 -3 1 3 2
Output
4 3 3 2 3 2 1