skokovi (COCI CONTEST_#1)
Time limit: 5 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: binary search

# Task Skokovi

In a land who knows where, in a world who knows when, lives a bee named Maya. Her adventure-filled life is an endless source of ideas for tasks, so we chose one of them.

Maya's friend, a grasshopper named Filip, is preparing for the Olympics in flower jumping. The flowers in the meadow can be represented as a sequence of positive integers *a* of length *N*. The height of each flower is given by the number *a<sub>i</sub>*.

Filip always jumps from left to right. Additionally, since this whole sport is new to him, he cannot jump to a flower whose height differs too much from the one he is currently on. Specifically, from flower *i*, he can jump to flower *j* if and only if *i < j* and |*a<sub>i</sub>* − *a<sub>j</sub>*| ≤ *K*, where *K* is a positive integer given in the input.

Help Maya plan Filip's training by determining which flowers Filip can reach if he starts on the leftmost flower. In other words, for each flower, determine if there is a sequence of jumps that leads to it, starting from the first flower.

## Input

The first line contains positive integers *N* (1 ≤ *N* ≤ 2 · 10<sup>5</sup>) and *K* (1 ≤ *K* ≤ 10<sup>9</sup>).

The second line contains a sequence of positive integers *a*, i.e., *N* numbers *a<sub>i</sub>* (1 ≤ *a<sub>i</sub>* ≤ 10<sup>9</sup>), representing the heights of the flowers.

## Output

In a single line, output *N* numbers, either 0 or 1, where each number indicates whether the corresponding flower is reachable. The number 0 means that it is not possible to reach that flower, while 1 means the flower is reachable. The first flower is always reachable as Filip starts from there.

## Scoring

| Subtask | Points | Constraints                             |
|---------|--------|-----------------------------------------|
| 1       | 20     | Flower heights are strictly increasing. |
| 2       | 25     | *N* ≤ 1000                            |
| 3       | 25     | No additional constraints.              |

## Examples

| input            | input               |
|------------------|---------------------|
| 5 2<br>5 4 8 7 2 | 5 3<br>10 15 14 8 9 |
| output           | output              |
| 1 1 0 1 1        | 1 0 0 1 1           |

## Clarification of the first example:

Filip can jump directly from the first flower to the second. The third flower is unreachable as Filip cannot jump to it from either the first or the second flower. To reach the fourth flower, Filip can also jump directly from the first flower. For the last flower, Filip needs to jump first to the second flower and then to the last flower.

Starter code:

Grader code:

Setup script:

Evaluation script: