题目描述

小蓝有一个栈，他不断地向这个栈的顶端添加数字。小蓝希望栈中不存在相同的数，当他加入了一个之前已经存在的数时，栈中之前存在的那个数会消失（其它原有元素的相对顺序不变），小蓝还想随时知道栈中所有相邻的数中和为奇数的总共有多少组，请你计算出小蓝要求的结果。

输入格式

输入的第一行包含一个整数 $n$。

接下来 $n$ 行，每行包含一个整数 $A_i$，表示被添加的数。

输出格式

输出 $n$ 行，每行包含一个整数表示每次添加数后的答案。

4
1
2
3
2

0
1
2
1

提示

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1 \leq n \leq 1000$，$A_i \leq 300$；
• 对于 $70\%$ 的评测用例，$1 \leq n \leq 10^5$，$A_i \leq 1000$；
• 对于所有评测用例，$1 \leq n \leq 5 \times 10^5$，$1 \leq A_i \leq 10^6$。