题目描述
对于一个由 0 和 1 组成的序列，我们定义它的“对称三元组”数量为满足 1≤l<m<r≤n 且 al=ar 的有序三元组 (l,m,r) 的个数。例如，“0110”的对称三元组数量为 2，因为包含两个对称三元组“010”。
给定一个长度为 n 的非负整数数组 b1,b2,…,bn，需要构造一个 01 串 S，使得对任意 1≤i≤n，S 的前缀长度为 i 时的对称三元组数量恰好等于 bi。若无解，输出 -1；否则输出任意一个可行解。
解题思路与方法
1. 前缀对称三元组增量公式
记当前已构造前缀长度为 i−1 的串为 S[1..i−1]，其对称三元组数量为 fi−1=bi−1。若在位置 i 处添加字符 b∈{0,1}，则新增的所有对称三元组都形如 bxb，其中中间字符 x 来自前缀中所有与 b 相等的位置。
- 设此前前缀中字符 b 出现次数为
c，下标和为 s（下标从 1 开始）；
题目内容
对于一个由 0 和 1 组成的序列，我们定义它的“对称三元组”数量为满足 1≤l<m<r≤n 且 al=ar 的有序三元组 (l,m,r) 的个数。例如，序列 010 中，位置 1 和 3 同为 0，中间的位置 2 可以构成三元组 (1,2,3)，因此对称三元组数量为 1。
现在给定一个长度为 n 的非负整数数组 b1,b2,…,bn。你需要构造一个长度为 n 的 01 序列，使得对于每个 i（1≤i≤n），该序列的前 i 个元素构成的对称三元组数量恰好等于 bi。如果存在多个解，输出任意一个即可；如果无法构造，则输出 -1。
数据范围：序列长度 n 不超过 105，数组中的每个数 bi 不超过 1015。
输入描述
第一行输入一个整数 n，表示待构造序列的长度。
第二行输入 n 个整数 b1,b2,…,bn，表示每个前缀要求的对称三元组数量。
