题目描述

小红定义一个字符串的权值为其长度为 3 的回文子序列数量。例如，“0110”的权值为 2，因为包含两个回文子序列“010”。
给定一个长度为 $n$ 的数组 $a$，需要构造一个 01 串 $S$，使得对任意 $1\le i\le n$，$S$ 的前缀长度为 $i$ 时的权值恰好等于 $a_i$。若无解，输出 -1；否则输出任意一个可行解。

解题思路与方法

1. 前缀权值增量公式

记当前已构造前缀长度为 $i-1$ 的串为 $S[1..i-1]$，其权值为 $f_{i-1}=a_{i-1}$。若在位置 $i$ 处添加字符 $b\in\{0,1\}$，则新增的所有长度 3 回文子序列都形如 $b\,x\,b$，其中中间字符 $x$ 来自前缀中所有与 $b$ 相等的位置。

• 设此前前缀中字符 $b$ 出现次数为 c，下标和为 s（下标从 1 开始）；
• 则新增回文数增量为 $\Delta_b =$$\sum_{j<i,,S_j=b}(i-j-1)

题目内容

小红定义一个字符串的权值为:其长度为3的回文子序列数量。

例如，“$0110$“ 的权值为 $2$ ，因为包含两个回文子序列 "$010$"。

现在给定一个长度为 $n$ 的数组。你需要构造一个 $01$ 串，满足其长度为 $i$ 的前缀的权值恰好是数组的第 $i$ 项。

输入描述

第一行输入一个正整数 $n$ ，代表待构造的字符串长度。

第二行输入一个长度为 $n$ 的数组，代表待构造的 $01$ 串每个长度的前缀权值。

$1≤n≤10^5$

$0≤a_i≤10^{15}$

输出描述

如果无解，请输出 $-1$ 。

否则输出一个长度为 $n$ 的 $01$ 串，有多解时输出任意即可。

样例1

输入

3
0 0 1

输出

010

说明

输出"$000$"、"$111$"或"$101$"均可。