← 返回 microsoft 的题目列表Balanced Prefix Permutation in a Permutation
类型：online_judge
You are given a permutation array p of length n containing each integer 1..n exactly once.
For each k (1 ≤ k ≤ n), determine whether there exists a contiguous subarray p[l..r] whose set of elements is exactly {1,2,...,k} (order does not matter).
If such a subarray exists, then k is called balanced.
Output a binary string s of length n where s[k-1] = '1' if k is balanced, otherwise '0'.
Input format (suggested)
Line 1: integer n
Line 2: n integers representing the permutation p
Output format
One line: a binary string of length n
Constraints
1 ≤ n ≤ 2*10^5
Examples
Input:
5
4 1 3 2 5
Output:
11011
Input:
4
1 2 3 4
Output:
1111
Input:
4
2 1 4 3
Output:
1100
Input:
1
1
Output:
1
Input:
6
6 5 4 3 2 1
Output:
100001
Example
Input
5
4 1 3 2 5
Output
11011