问题描述

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

输入格式

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

输出格式

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

4
1
2
3
2

0
1
2
1

评测用例规模与约定

对于 $30\%$ 的评测用例，$1≤n≤1000$，$A_i≤300$；

对于 $70\%$ 的评测用例，$1≤n≤10^5$，$A_i≤1000$；

对于所有评测用例，$1≤n≤5×10^5$，$1≤A_i≤10^6$。