Balanced Array
Ham 先生喜欢平衡。他把平衡的概念应用到了整数数组上。
称整数数组 a1,a2,…,al 为平衡数组,当且仅当存在一个整数 k,满足:
- 1≤k≤⌊2l−1⌋;
- 对每个 i=1,2,…,l−2k,都有 ai+ai+2k=2ai+k。
给定数组 a1,a2,…,an,请对每个 l=1,2,…,n,判断前缀 a1,a2,…,al 是否为平衡数组。
输入格式
第一行包含一个整数 n(1≤n≤2×106),表示数组的长度。
第二行包含 n 个整数 a1,a2,…,an(1≤ai≤2×108)。为了减小输入文件的大小,这些整数使用六十二进制表示,由空白分隔。
六十二进制的数字字符 0…9、a…z、A…Z 依次表示数值 0…61。大小写字母的取值不同。例如,Aa0 表示
36×622+10×62+0=139004.
第一行的 n 仍用通常的十进制表示。输入只有一个数组。
输出格式
输出一个长度恰为 n 的二进制字符串 s1s2⋯sn。当前缀 a1,…,al 为平衡数组时,sl=1;否则 sl=0。
样例 1
3
1 2 3
001
样例 2
9
1 2 3 2 5 4 3 8 5
001010111
样例 3
9
1C 3f 4S 3h 88 6x 4W d1 8c
001010111