「KDOI-06-J」翻转与反转

题目描述

小 W 有一个长度为 $n$ 的 $01$ 序列 $a_1,a_2,\ldots,a_n$，他将对这个序列按顺序进行 $n$ 次操作。

在第 $i$ 次操作中（$1\le i\le n$），小 W 将按顺序执行以下两种变换：

1. 将区间 $[1,i]$ 中的数按下标翻转。形式化地说，在这次变换之后，序列 $a$ 将变为 $a_i,a_{i-1},\ldots,a_{1},a_{i+1},a_{i+2},\ldots,a_n$。
2. 将区间 $[1,i]$ 中的数按值翻转。形式化地说，在这次变换之后，对于任意 $1\le j\le i$，若 $a_j=0$，则 $a_j$ 将变为 $1$，否则 $a_j$ 将变为 $0$。

小 W 想要知道，在全部 $n$ 次操作结束后，序列 $a$ 中每个元素的值。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$，表示序列长度。

接下来一行 $n$ 个整数，表示序列 $a_1,a_2,\ldots, a_n$。保证 $a_i=0$ 或 $1$。

输出格式

输出到标准输出。

输出包含一行 $n$ 个整数，表示操作结束后序列 $a$ 中每个元素的值。

样例 #1

样例输入 #1

3
1 1 1

样例输出 #1

0 0 1

样例 #2

样例输入 #2

8
1 0 1 1 1 0 0 1

样例输出 #2

0 1 0 1 1 1 1 0

提示

【样例解释 #1】

序列 $a$ 的变化如下表所示：

操作次数	序列 $a$ 的变化
$1$	$[1,1,1]\to [1,1,1]\to[0,1,1]$
$2$	$[0,1,1]\to [1,0,1]\to[0,1,1]$
$3$	$[0,1,1]\to [1,1,0]\to[0,0,1]$

【样例解释 #2】

序列 $a$ 的变化如下表所示：

操作次数	操作后的序列 $a$
-	$[1,0,1,1,1,0,0,1]$
$1$	$[0,0,1,1,1,0,0,1]$
$2$	$[1,1,1,1,1,0,0,1]$
$3$	$[0,0,0,1,1,0,0,1]$
$4$	$[0,1,1,1,1,0,0,1]$
$5$	$[0,0,0,0,1,0,0,1]$
$6$	$[1,0,1,1,1,1,0,1]$
$7$	$[1,0,0,0,0,1,0,1]$
$8$	$[0,1,0,1,1,1,1,0]$

【样例 #3】

见选手文件中的 revflip/revflip3.in 与 revflip/revflip3.ans。

【样例 #4】

见选手文件中的 revflip/revflip4.in 与 revflip/revflip4.ans。

【数据范围】

对于所有数据保证：$1\le n\le 2\times 10^6$，且对于任意 $1\le i\le n$，$a_i=0$ 或 $1$。

测试点编号	$n\le$	特殊性质
$1\sim 3$	$10^3$	无
$4\sim 5$	$10^5$
$6 \sim 7$	$2\times 10^6$	$a_i=0$
$8\sim 10$		无