题目内容

给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$。记 $M$ 为整个序列中的最大值，称为基准值。

对于每一个位置 $i$，如果存在某个 $j > i$，使得 $a_i \oplus a_j \ge M$（$\oplus$ 表示按位异或），则称位置 $i$ 是优质位置。

请判断序列中每个位置是否为优质位置。

约束条件：序列长度 $n$ 满足 $1 \le n \le 200\,000$，所有整数满足 $1 \le a_i \le 10^9$。

输入描述

输入共两行。 第一行包含一个整数 $n$（$1 \le n \le 200\,000$），表示序列长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示序列中的元素。

输出描述

输出一行一个长度为 $n$ 的字符串，仅由字符 0 和 1 组成。如果位置 $i$ 是优质位置，则第 $i$ 个字符为 1，否则为 0。

样例1

输入

1
100

输出

0

说明

序列仅有一个元素 $a_1 = 100$，最大值 $M = 100$。对于位置 1，不存在 $j > 1$，因此不满足优质位置的条件，输出 0。

样例2

输入

3
1 2 3

输出

100

说明

最大值 $M = 3$。

• 位置 3（$a_3=3$）右侧无元素，不是优质位置，记为 0。
• 位置 2（$a_2=2$）右侧仅有 $a_3=3$，$2 \oplus 3 = 1 < M$，不满足条件，记为 0。
• 位置 1（$a_1=1$）右侧有 $a_2=2$ 和 $a_3=3$，其中 $1 \oplus 2 = 3 \ge M$，满足条件，记为 1。 因此最终输出 100。

样例3

输入

3
5 1 5

输出

000

说明

最大值 $M = 5$。

• 位置 3 右侧无元素，为 0。
• 位置 2 右侧有 $a_3=5$，$1 \oplus 5 = 4 < M$，为 0。
• 位置 1 右侧有 $1$ 和 $5$，$5 \oplus 1 = 4$，$5 \oplus 5 = 0$，均小于 $M$，为 0。 最终输出 000。

样例4

输入

5
8 1 2 4 8

输出

11110

说明

最大值 $M = 8$。

• 位置 5 为最后一个，记为 0。
• 位置 4（$a_4=4$）右侧有 $a_5=8$，$4 \oplus 8 = 12 \ge M$，记为 1。
• 位置 3（$a_3=2$）右侧有 $4$ 和 $8$，$2 \oplus 8 = 10 \ge M$，记为 1。
• 位置 2（$a_2=1$）右侧有 $2,4,8$，$1 \oplus 8 = 9 \ge M$，记为 1。
• 位置 1（$a_1=8$）右侧有 $1,2,4,8$，$8 \oplus 4 = 12 \ge M$，记为 1。 最终输出 11110。