#P18451. Balanced Array

Balanced Array

Balanced Array

Ham 先生喜欢平衡。他把平衡的概念应用到了整数数组上。

称整数数组 a1,a2,…,ala_1,a_2,\ldots,a_l 为平衡数组,当且仅当存在一个整数 kk,满足:

  • 1≤k≤⌊l−12⌋1\le k\le\left\lfloor\dfrac{l-1}{2}\right\rfloor;
  • 对每个 i=1,2,…,l−2ki=1,2,\ldots,l-2k,都有 ai+ai+2k=2ai+ka_i+a_{i+2k}=2a_{i+k}。

给定数组 a1,a2,…,ana_1,a_2,\ldots,a_n,请对每个 l=1,2,…,nl=1,2,\ldots,n,判断前缀 a1,a2,…,ala_1,a_2,\ldots,a_l 是否为平衡数组。

输入格式

第一行包含一个整数 nn(1≤n≤2×1061\le n\le2\times10^6),表示数组的长度。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤2×1081\le a_i\le2\times10^8)。为了减小输入文件的大小,这些整数使用六十二进制表示,由空白分隔。

六十二进制的数字字符 0…9、a…z、A…Z 依次表示数值 00…6161。大小写字母的取值不同。例如,Aa0 表示

36×622+10×62+0=139004.36\times62^2+10\times62+0=139004.

第一行的 nn 仍用通常的十进制表示。输入只有一个数组。

输出格式

输出一个长度恰为 nn 的二进制字符串 s1s2⋯sns_1s_2\cdots s_n。当前缀 a1,…,ala_1,\ldots,a_l 为平衡数组时,sl=1s_l=1;否则 sl=0s_l=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