Balanced prefixes in a permutation

You are given a permutation p of length n: every integer from 1 to n appears exactly once, in some order.

Call a number k (with 1 <= k <= n) balanced if some contiguous subarray p[l..r] contains exactly the values 1, 2, ..., k, each once, in any order.

Implement:

def balanced_numbers(p: list[int]) -> str

Return a string of length n whose k-th character (1-indexed) is '1' if k is balanced and '0' otherwise.

Constraints

• 1 <= n <= 2 * 10^5
• p is a permutation of 1..n
• Aim for better than O(n²).

Example 1

p = [3, 1, 2, 5, 4]
output: "11101"

• k = 1: [1] works.
• k = 2: [1, 2] works.
• k = 3: [3, 1, 2] works.
• k = 4: the values 1..4 are spread over indices 0..4, and that range also holds 5, so no window works.
• k = 5: the whole array works.

Example 2

p = [2, 4, 1, 3]
output: "1001"

For k = 2, the shortest window that holds both 1 and 2 is [2, 4, 1], which also contains 4.