#arc128a. [arc128_a]Gold and Silver

[arc128_a]Gold and Silver

题目描述

Snuke 现在有 11 克黄金和 00 克白银。他将在接下来的 NN 天进行黄金和白银的交易。每天,他有两个选择:什么都不做,或者进行一次交易。如果他在第 ii 天进行交易(1iN1 \leq i \leq N),则会发生以下情况。

  • 如果交易之前他有 xx 克黄金,那么全部换成 x×Aix \times A_i 克白银。另一方面,如果他有 xx 克白银,那么全部换成 x/Aix / A_i 克黄金。

Snuke 的目标是最大化最后拥有的黄金数量。找出一种实现他目标的方式。

约束条件

  • 2N2000002 \leq N \leq 200000
  • 1Ai1091 \leq A_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出:

NN A1A_1 A2A_2 \cdots ANA_N

输出

按照以下格式输出答案:

v1v_1 v2v_2 \cdots vNv_N

其中,viv_i 是表示第 ii 天行动的整数(0vi10 \leq v_i \leq 1)。vi=0v_i=0 表示什么都不做,vi=1v_i=1 表示进行一次交易。如果有多个可能的解决方案,输出任何一个都被视为正确。


示例输入 1

3
3 5 2

示例输出 1

0 1 1

最佳行动序列如下。

  • 11 天:什么都不做。

  • 22 天:将 11 克黄金换成 55 克白银。

  • 33 天:将 55 克白银换成 2.52.5 克黄金。


示例输入 2

4
1 1 1 1

示例输出 2

0 0 0 0

例如,(v1,v2,v3,v4)=(1,1,1,1)(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