Problem Brief

Get Balanced String

FULLTIMEOA

Given an array arr of length n which is a permutation of 1, 2, ..., n, a number k is called balanced if there exist two indices i and j such that arr[i], arr[i+1], ..., arr[j] is a permutation of 1, 2, ..., k.

Return a binary string of length n, where the character at 0-indexed position k-1 is '1' if k is balanced, and '0' otherwise.

1Example 1

Input

arr = [4, 1, 3, 2]

Output

1011

Explanation

k=1: subarray [1] is a permutation of {1} → balanced.
k=2: no contiguous subarray equals {1, 2} → not balanced.
k=3: subarray [1, 3, 2] is a permutation of {1, 2, 3} → balanced.
k=4: full array [4, 1, 3, 2] is a permutation of {1, 2, 3, 4} → balanced.

2Example 2

Input

arr = [1, 2, 3]

Output

111

Explanation

For every k from 1 to 3, the prefix arr[0..k-1] is already a permutation of {1, ..., k}.

3Example 3

Input

arr = [2, 3, 1]

Output

101

Explanation

k=1: subarray [1] exists → balanced.
k=2: no contiguous subarray is exactly {1, 2} — elements 1 and 2 are separated by 3 → not balanced.
k=3: full array [2, 3, 1] is a permutation of {1, 2, 3} → balanced.

4Example 4

Input

arr = [1]

Output

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n ≤ 10⁵
arr is a permutation of 1, 2, ..., n