В подземелье есть $$$(n+1)$$$ комнат, последовательно соединенных $$$n$$$ переходами. Комнаты пронумерованы от $$$0$$$ до $$$n$$$, а переходы — от $$$1$$$ до $$$n$$$, и $$$i$$$-й переход соединяет комнаты $$$(i-1)$$$ и $$$i$$$.
Каждый переход оснащен охранным устройством одного из двух типов. Охранное устройство первого типа при переходе проверяет наличие пропуска определенного цвета, и запрещает проход, если пропуск такого цвета недействителен. Охранное устройство второго типа никогда не запрещает проход, но при проходе пропуск определенного цвета аннулируется и становится недействительным.
В начале вы обладаете всеми возможными пропусками и находитесь в комнате $$$s$$$. Для каждого возможного $$$s$$$ от $$$0$$$ до $$$(n-1)$$$ выведите, как много комнат можно пройти в направлении комнаты $$$n$$$.
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 500000$$$) — количество переходов.
Во второй строке дано $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le |a_i| \le n$$$). Число $$$|a_i|$$$ — цвет пропуска, с которым работает $$$i$$$-й переход. Если $$$a_i > 0$$$, то $$$i$$$-й переход — первого типа, а если $$$a_i < 0$$$ — второго типа.
Выведите $$$n$$$ целых чисел через пробел: ответ на задачу для каждого возможного $$$s$$$ от $$$0$$$ до $$$(n-1)$$$.
6 1 -1 -1 1 -1 1
3 2 1 2 1 1
7 2 -1 -2 -3 1 3 2
4 3 3 2 3 2 1
