Balanced Numbers in a Permutation

You are given a permutation p of length n.

A number k is called balanced if there exists a contiguous subarray p[l..r] whose elements form a permutation of the numbers 1, 2, ..., k.

For every k from 1 to n, determine whether k is balanced. Return a binary string of length n where the kth character is:

• "1" if k is balanced
• "0" otherwise

A permutation of length n contains every integer from 1 to n exactly once.

Examples

Example 1:

Input: p = [4, 1, 3, 2]

Output: "1011"

Explanation:

1, 3, and 4 are balanced, but 2 is not. For example, [1, 3, 2] is a contiguous permutation of 1..3.

Example 2:

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

Output: "11111"

Explanation:

For every k from 1 to 5, the values 1..k occupy a contiguous block somewhere in the permutation.

Example 3:

Input: p = [2, 4, 1, 3]

Output: "1001"

Explanation:

Only 1 and 4 are balanced. The values 1..2 and 1..3 do not fit inside a contiguous block of lengths 2 and 3.

Constraints

• 1 <= p.length <= 2 * 10^5
• p is a permutation of the integers from 1 to p.length