A - Gold and Silver Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

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

入力例 1

3
3 5 2

出力例 1

0 1 1

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

  • 1 日目: なにもしない．

  • 2 日目: 1 グラムの金を銀と交換し，5 グラムの銀を得る．

  • 3 日目: 5 グラムの銀を金と交換し，2.5 グラムの金を得る．

入力例 2

4
1 1 1 1

出力例 2

0 0 0 0

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

入力例 3

10
426877385 186049196 624834740 836880476 19698398 709113743 436942115 436942115 436942115 503843678

出力例 3

1 1 0 1 1 1 1 0 0 0

Score : 400 points

Problem Statement

Snuke has 1 gram of gold and 0 grams of silver now. He will do trading of gold and silver for the following N days. On each day, he has two choices: do nothing, or make a trade. If he trades on Day i (1 \leq i \leq N), the following will happen.

  • If he has x grams of gold before the trade, exchange all of it for x \times A_i grams of silver. On the other hand, if he has x grams of silver, exchange all of it for x / A_i grams of gold.

Snuke's objective is to maximize the amount of gold he has in the end. Find one way to achieve his objective.

Constraints

  • 2 \leq N \leq 200000
  • 1 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer in the following format:

v_1 v_2 \cdots v_N

Here, v_i is an integer representing the action on Day i (0 \leq v_i \leq 1). v_i=0 means he does nothing, and v_i=1 means he makes a trade. If there are multiple possible solutions, printing any of them will be considered correct.

Sample Input 1

3
3 5 2

Sample Output 1

0 1 1

The optimal sequence of actions is as follows.

  • Day 1: Do nothing.

  • Day 2: Exchange 1 gram of gold for 5 grams of silver.

  • Day 3: Exchange 5 grams of silver for 2.5 grams of gold.

Sample Input 2

4
1 1 1 1

Sample Output 2

0 0 0 0

(v_1,v_2,v_3,v_4)=(1,1,1,1), for example, is also considered correct.

Sample Input 3

10
426877385 186049196 624834740 836880476 19698398 709113743 436942115 436942115 436942115 503843678

Sample Output 3

1 1 0 1 1 1 1 0 0 0