题目描述

すぬけくんは今，$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$ ならば交換をすることを表す． なお，答えが複数通り存在する場合，そのどれを出力しても正解とみなされる．

题目大意

你最近在做金银交易，在接下来的 $N$ 天中，每天都有一个汇率 $A_i$。起初你有 $1$克金，没有银。

每天你可以兑换手中的金银（也可以不兑换），如果你手中有 $x$ 克金，可以全部兑换为 $x \times A_i$ 克银，同理，如果有 $x$ 克银，可以全部兑换为 $x / A_i$ 克金。

请问 $N$ 天后最多能得到多少克金。你只需要输出方案。

3
3 5 2

0 1 1

4
1 1 1 1

0 0 0 0

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$
• 入力される値はすべて整数である

Sample Explanation 1

以下のように行動するのが最適です． - $1$ 日目: なにもしない． - $2$ 日目: $1$ グラムの金を銀と交換し，$5$ グラムの銀を得る． - $3$ 日目: $5$ グラムの銀を金と交換し，$2.5$ グラムの金を得る．

Sample Explanation 2

$(v_1,v_2,v_3,v_4)=(1,1,1,1)$ なども正解とみなされます．