P17716 [HexOI Round 1] 变魔术 / magic

题目来源：【HT-130-Div.3】核桃 CSP-J 组模拟赛 [HexOI](https://www.luogu.com.cn/team/85094) 欢迎您。

小 Hex 有 $n$ 块积木！每块积木都有一个「美丽度」，第 $i$ 块积木的美丽度为 $a_i$。 现在小 Hex 想向小 Toast 表演魔术。他希望用一种特殊的魔术技巧来整理他的积木，最后只留下小 Toast 最喜欢的积木。 具体地，他整理积木的方法如下： 1. 小 Hex 有一个淘汰盒。初始时，他手上有所有的积木，并且淘汰盒是空的。 2. 小 Hex 会把他目前手上所有的积木分为若干堆，并计算每堆所有积木的美丽度之和； 3. 小 Hex 会选择美丽度之和最高的一堆积木（如果有并列则任取一堆），保留这一堆积木，并把其他所有的积木放到淘汰盒中； 4. 如果操作结束后小 Hex 只剩恰好一个积木，那么他会把这个积木展示给小 Toast；否则，回到「第 2 步」继续。 然而，小 Hex 并不知道小 Toast 最喜欢的积木，因此他要对所有的情况做好准备。现在他想知道，对于所有的 $i=1,2,\cdots,n$，假设小 Toast 喜欢第 $i$ 块积木，他能否恰好选择出小 Toast 喜欢的那个积木？

第一行一个正整数 $n$。 第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$。

一行 $n$ 个整数，第 $i$ 个数表示假设小 Toast 喜欢第 $i$ 块积木时，小 Hex 能否恰好选出他喜欢的积木。为 $1$ 表示可以，为 $0$ 表示不行。

#### 【样例 1 解释】 小 Hex 可以用下面的方法来选出第二块积木： - 把所有积木按编号分为 $\{1,2\}$ 和 $\{3\}$ 两堆积木，此时两堆积木的美丽度之和分别为 $3,3$。保留第一堆积木，将 $3$ 号积木放进淘汰盒。 - 把 $1,2$ 号积木按编号分为 $\{1\}$ 和 $\{2\}$ 两堆积木，此时两堆积木的美丽度之和分别为 $1,2$。保留第二堆积木，将 $1$ 号积木放进淘汰盒。 - 此时，小 Hex 只剩下 $2$ 号积木。 小 Hex 可以用下面的方法来选出第三块积木： - 把所有积木按编号分为 $\{1\}$，$\{2\}$ 和 $\{3\}$ 三堆积木，此时三堆积木的美丽度之和分别为 $1,2,3$。保留第三堆积木，将 $1,2$ 号积木放进淘汰盒。 - 此时，小 Hex 只剩下 $3$ 号积木。 可以证明，无论小 Hex 怎样操作，他都无法选出第一块积木。 #### 【样例 3】 见选手目录下的 magic/magic3.in 与 magic/magic3.ans。 该样例满足测试点 $4,5$ 的约束条件。 #### 【样例 4】 见选手目录下的 magic/magic4.in 与 magic/magic4.ans。 该样例满足测试点 $7\sim 9$ 的约束条件。 #### 【样例 5】 见选手目录下的 magic/magic5.in 与 magic/magic5.ans。 该样例满足测试点 $10\sim 12$ 的约束条件。 #### 【样例 6】 见选手目录下的 magic/magic6.in 与 magic/magic6.ans。 该样例满足测试点 $13\sim 20$ 的约束条件。 #### 【数据范围】 对于所有测试数据，保证： - $1\leq n\leq 10^5$。 - 对于所有 $1\leq i\leq n$，均有 $1\leq a_i\leq 10^9$。 ::cute-table{tuack} |测试点编号| $n$ | $a_i(1\leq i\leq n)$ | 特殊性质 | |:--:|:--:|:--:|:--:| |$1$|$\leq 3$|$\leq 10^9$|无| |$2,3$|$\leq 10$|^|^| |$4,5$|$\leq 5\times 10^3$|$\leq 2$|^| |$6$|^|$\leq 10^9$|A| |$7\sim 9$|^|^|B| |$10\sim 12$|^|^|无| |$13\sim 20$|$\leq 10^5$|^|无| 特殊性质 A：保证 $a_1=a_2=\cdots=a_n$。 特殊性质 B：对于所有 $i(1\leq i\leq n)$，都有 $a_i=10^9$ 或 $a_i=10^9-1$。