Find all balanced k in a permutation

You are given a permutation $p$ of length $n$ containing each integer from $1$ to $n$ exactly once.

For each $k$ where $1 \le k \le n$, determine whether there exists a contiguous subarray of $p$ whose elements are exactly the set $\{1,2,\dots,k\}$ (in any order).

• If such a subarray exists, call $k$ balanced.
• Output a binary string $s$ of length $n$ where $s[k]$ (1-based) is '1' if $k$ is balanced, otherwise '0'.

Input

• Integer $n$
• Array $p$ of length $n$, a permutation of $[1..n]$

Output

• A string of length $n$ consisting of '0' and '1'

Notes / expectations

• Aim for an efficient algorithm (e.g., $O(n)$ or $O(n \log n)$), not enumerating all subarrays.

Find All Balanced k in a Permutation

Constraints

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

Examples

Example 1

Input: (5, [3, 1, 2, 5, 4])
Output: '11101'

Explanation: For k = 1, 2, and 3, the positions of {1..k} form contiguous segments. For k = 4 they do not. For k = 5, the whole array works.

Example 2

Input: (5, [2, 1, 4, 3, 5])
Output: '11011'

Explanation: The sets {1}, {1,2}, {1,2,3,4}, and {1,2,3,4,5} each occupy contiguous positions, but {1,2,3} does not.

Hints

1. Instead of checking every subarray, think about where each value 1, 2, ..., k appears in the permutation.
2. For a fixed k, the values 1 through k form a valid contiguous subarray exactly when their minimum and maximum positions span a segment of length k.