题目描述

すぬけくん现在拥有 $1$ 克黄金和 $0$ 克白银。他将在接下来的 $N$ 天内进行黄金与白银的交易。每天，他可以选择“什么都不做”或“进行交换”这两种操作中的一种。在第 $i$ 天（$1 \leq i \leq N$）进行交换时，会发生以下情况：

• 如果交换前他持有 $x$ 克黄金，则他会将所有黄金全部兑换成白银，获得 $x \times A_i$ 克白银。反之，如果他持有 $x$ 克白银，则会将所有白银全部兑换成黄金，获得 $x / A_i$ 克黄金。

すぬけくん的目标是最终持有的黄金数量最大。请你求出一种能实现他目标的操作方案。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

请按如下格式输出答案：

$v_1$ $v_2$ $\cdots$ $v_N$

其中 $v_i$ 是第 $i$ 天的操作，$0 \leq v_i \leq 1$，$v_i=0$ 表示什么都不做，$v_i=1$ 表示进行交换。如果存在多种方案，只需输出其中一种即可。

样例 1

输入

3
3 5 2

输出

0 1 1

样例 2

输入

4
1 1 1 1

输出

0 0 0 0

样例 3

输入

10
426877385 186049196 624834740 836880476 19698398 709113743 436942115 436942115 436942115 503843678

输出

1 1 0 1 1 1 1 0 0 0

说明/提示

限制条件

• $2 \leq N \leq 200000$
• $1 \leq A_i \leq 10^9$
• 所有输入的值均为整数

样例解释 1

如下操作是最优的：

• 第 $1$ 天：什么都不做。
• 第 $2$ 天：将 $1$ 克黄金兑换成 $5$ 克白银。
• 第 $3$ 天：将 $5$ 克白银兑换成 $2.5$ 克黄金。

样例解释 2

例如 $(v_1,v_2,v_3,v_4)=(1,1,1,1)$ 这样的方案也被认为是正确的。

由 ChatGPT 4.1 翻译