← 返回题目列表

AtCoder · agc028_e

E. 高元素

中文机器翻译题面 查看原题

分数: 1400 点

问题陈述

你被给予 P,排列 (1,\ 2,\ ...\ N).

一个字符串 S 长度 N 组成 0 和 1 是 好字符串 当满足以下条件时:

  • 序列 满足条件的 X 和 Y 的构造如下:
    • 首先,让 X 和 Y 是空序列。
    • 对于每个 i=1,\ 2,\ ...\ N,按此顺序,附加 P_i 到年底 X if S_i= 0,并将其附加到末尾 Y if S_i= 1.
  • If X 和 Y 有相同数量的 高 元素, S 是一个很好的字符串。 在这里, i序列的第一个元素被称为 高 当该元素是来自 1-st 至 i- 序列中的第一个元素。

确定是否存在好的字符串。如果存在,则找到字典顺序最小的此类字符串。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq N
  • P_1,\ P_2,\ ...\ P_N 都是不同的。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
P_1 P_2 ... P_N

输出

如果不存在好的字符串,则打印 -1。 如果存在,则打印按字典顺序最小的此类字符串。


示例输入 1

6
3 1 4 6 2 5

示例输出 1

001001

让 S= 001001。然后, X=(3,\ 1,\ 6,\ 2) 和 Y=(4,\ 5)。 中的高元素 X 是第一个和第三个元素,其中的高元素 Y 是第一个和第二个元素。 由于它们具有相同数量的高元素, 001001 是一个很好的字符串。 没有比这个更小的字符串,所以答案是 001001.


示例输入 2

5
1 2 3 4 5

示例输出 2

-1

示例输入 3

7
1 3 2 5 6 4 7

示例输出 3

0001101

示例输入 4

30
1 2 6 3 5 7 9 8 11 12 10 13 16 23 15 18 14 24 22 26 19 21 28 17 4 27 29 25 20 30

示例输出 4

000000000001100101010010011101