配点 : $400$ 点

問題文

すぬけくんは今，$1$ グラムの金と $0$ グラムの銀を持っています． 彼はこれから $N$ 日かけて金と銀の取引を行います． それぞれの日で，"なにもしない" もしくは "交換をする" のいずれかの行動をとります． $i$ 日目 ($1 \leq i \leq N$) に交換をする場合，以下のことが起こります．

• 交換前に金を $x$ グラム持っていた場合，それらをすべて銀と交換し，$x \times A_i$ グラムの銀を得る． 逆に，銀を $x$ グラム持っていた場合，それらをすべて金と交換し，$x / A_i$ グラムの金を得る．

すぬけくんの目標は，最終的に持っている金の量を最大化することです． 彼の目標を達成するような方法を一つ求めてください．

制約

• $2 \leq N \leq 200000$
• $1 \leq A_i \leq 10^9$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

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

3
3 5 2

0 1 1

以下のように行動するのが最適です．

• $1$ 日目: なにもしない．
• $2$ 日目: $1$ グラムの金を銀と交換し，$5$ グラムの銀を得る．
• $3$ 日目: $5$ グラムの銀を金と交換し，$2.5$ グラムの金を得る．

4
1 1 1 1

0 0 0 0

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

10
426877385 186049196 624834740 836880476 19698398 709113743 436942115 436942115 436942115 503843678

1 1 0 1 1 1 1 0 0 0