Problem Brief

Balanced Prefix Sets in a Permutation

FULLTIMEOA

You are given a permutation p of the integers 1 through n.

For each k from 1 to n, determine whether there exists a contiguous subarray whose set of values is exactly {1, 2, ..., k}.

Build a binary string of length n. The k-th character should be '1' if such a subarray exists for that k, otherwise it should be '0'.

Function Description

Complete the function balancedPrefixSetsMask in the editor below.

balancedPrefixSetsMask has the following parameter:

int[] p: a permutation of 1..n

Returns

String: a binary string whose k-th character indicates whether {1, 2, ..., k} appears as the value set of some contiguous subarray.

1Example 1

Input

p = [2, 1, 4, 3]

Output

"1101"

Explanation

For k = 1, the subarray [1] works. For k = 2, the subarray [2, 1] works. For k = 3, the values {1, 2, 3} do not occupy a contiguous span. For k = 4, the whole array works.

2Example 2

Input

p = [3, 1, 2, 5, 4]

Output

"11101"

Explanation

The sets {1}, {1, 2}, and {1, 2, 3} all appear within contiguous spans. The set {1, 2, 3, 4} does not. The whole array gives {1, 2, 3, 4, 5}.

Constraints

Limits and guarantees your solution can rely on.

The source thread did not provide explicit numeric bounds.

p is a permutation of the integers 1..n.
The output string has length n.
Each character is either '1' or '0'.