Which prefixes of 1..n appear as a contiguous block

You are given an array p of length n that is a permutation of the integers 1..n (each value appears exactly once).

For every k from 1 to n, decide whether p has a contiguous subarray of length exactly k whose elements are the values 1, 2, ..., k in some order.

Implement:

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

Return a string of length n whose k-th character (1-indexed) is '1' if such a subarray exists for k, and '0' otherwise.

Constraints

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

Example 1

p = [3, 1, 4, 2] returns "1001".

• k = 1: [1] works.
• k = 2: 1 and 2 are at indices 1 and 3, so no window of length 2 holds both.
• k = 3: any window holding 1, 2, 3 also holds 4.
• k = 4: the whole array works.

Example 2

p = [4, 2, 1, 3, 5] returns "11111": the windows [1], [2, 1], [2, 1, 3], [4, 2, 1, 3] and the whole array all work.