Problem: Papa and Baby Frog

Want to try solving this problem? You can submit your code online if you log in or register.

Papa and Baby Frog

Time limit: 1 second
Memory limit: 256 MiB

Papa and Baby frog live among a line of n equally-spaced stones, numbered 1 to n, from left to right. Stone i has a positive integer height h_i.

The frogs can jump between stones, and do so, according to the following rules:

A single jump moves Papa frog to the closest stone that has a strictly greater height than his current stone. If there are multiple options, he chooses the rightmost among these;
A single jump moves Baby frog to the closest stone that has a strictly smaller height than her current stone. If there are multiple options, she chooses the rightmost among these.

Papa frog would like to choose a stone to be home, and a different stone to be school. He requires that:

Papa frog can jump from home to school, in no more than k jumps; and
Baby frog can jump from school to home, in no more than k jumps.

A stone is called a potential home if there is at least one other stone that can be chosen as school, if this stone is chosen as home.

Your task is to help the frogs determine which stones are potential homes.

Subtasks and Constraints

For all subtasks, you are guaranteed that:

n ≥ 2
1 ≤ k ≤ n
For all stones i, 1 ≤ h_i ≤ 1,000,000,000

Additional constraints for each subtask are given below.

Subtask	Points	n	k
1	10	n ≤ 2000	k = 1
2	10	n ≤ 2000	k ≤ 5
3	20	n ≤ 2000	k ≤ 100
4	20	n ≤ 2000	k ≤ n
5	20	n ≤ 100,000	k ≤ 5
6	10	n ≤ 100,000	k = n
7	10	n ≤ 100,000	k ≤ n

Input

The first line of input contains the two integers, n and k.

The second line of input contains n integers h₁,..., h_n, which are the heights of the stones.

Output

The output should contain a string of n characters on a single line. The i-th of these characters should be 1, if stone i is a potential home, or 0, otherwise.

Sample Input 1

4 1
4 1 3 2

Sample Output 1

Sample Input 2

7 2
3 1 2 1 2 2 3

Sample Output 2

Sample Input 3

10 3
10 5 6 4 7 3 8 2 9 1

Sample Output 3

0000010001

Explanation

In the first example, only stone 4 can be chosen as home, when stone 3 is chosen as school. Hence, stone 4 is the only potential home.

In the second example:

Stone 2 can be chosen as home, when stone 1 is chosen as school. Papa frog jumps through stones 2→3→1, whereas Baby frog jumps directly from stone 1 to stone 2.
Stone 4 can be chosen as home, when stone 5 is chosen as school. Papa and Baby frog both jump directly between home and school, and vice-versa.
Stone 6 can be chosen as home, when stone 7 is chosen as school. Papa and Baby frog both jump directly between home and school, and vice-versa.

Hence, stones 2, 4 and 6 are potential homes.

In the third example:

Stone 6 can be chosen as home, when stone 1 is chosen as school. Papa frog jumps through stones 6→7→9→1, whereas Baby frog jumps through stones 1→2→4→6.
Stone 10 can be chosen as home, when stone 9 is chosen as school. Papa and Baby frog both jump directly between home and school, and vice-versa.

Hence, stones 6 and 10 are potential homes.