405898: GYM102154 D Robomarathon

There are n robots participating in the robomarathon, numbered from 1 to n. Robots must cover the same distance, moving along adjacent tracks, each with a width of 1 meter. The i-th robot is in the i-th track and it needs a_i seconds to cover the required distance and get to the finish line.

A signal device is installed at the start point of each robot. To make the competition less predictable, the judges decided to turn some devices off before the contest. The remaining devices are active. There must be at least one active device.

When the chief judge starts the robomarathon, all active devices send a signal. A robot begins to move at the moment when it gets a signal from some active device. The signal propagates at the rate of 1 meter per second. The distance between tracks i and j is |i - j| meters.

Let x_i denote the distance from the i-th track to the nearest track with an active device. The i-th robot will start moving x_i seconds after the start and get to the finish line in a_i seconds, so it will finish in f_i = x_i + a_i seconds after the start of the robomarathon.

Let k_i be the number of robots that finished strictly before the i-th robot. The place of this robot in the robomarathon is k_i + 1. If multiple robots finish at the same time, then all of them have the place k + 1 if k robots have finished before that.

Consider the following example. Let n = 3, a₁ = 2, a₂ = 3 and a₃ = 5. If the only active signal device is in the third track, the first robot starts moving 2 seconds after the start and finishes at f₁ = 2 + 2 = 4. The second robot starts moving 1 seconds after the start, f₂ = 1 + 3 = 4. The third robot starts moving immediately at the start, f₃ = 0 + 5 = 5. Robots 1 and 2 share the first place, while robot 3 takes the third place. If all three devices work correctly, robots finish with times f₁ = 2, f₂ = 3, f₃ = 5. Robot 1 has the first place, robot 2 the second place, and robot 3 the third place.

As you can see from the example, the leaderboard depends on which devices are active. You will be asked to answer one of two possible questions:

1. For each robot, determine the minimum place it can get.
2. For each robot, determine the maximum place it can get.

Your task is to write a program that, given the times a_i and the type of the request, determines the corresponding best/worst place each robot can take.

The first line of the input contains two integers n and p (1 ≤ n ≤ 400 000, 1 ≤ p ≤ 2) — the number of robots and the type of the request. The value p = 1 means you need to determine the minimum place a robot can take, while p = 2 means you need to determine the maximum place a robot can take.

The second line contains n integers a₁, a₂, ..., a_n — the time each robot needs to cover the distance to the finish line (1 ≤ a_i ≤ 10⁹).

Print n lines. The i-th line of the output should contain one integer — the minimum or the maximum place of the i-th robot, as the value p specifies.

The subtask 3 includes 30 tests, each independently scored 1 point if correct. You get 0 points for them anyway if you don't get the full score in subtask 1.

The subtask 4 includes 50 tests, each independently scored 1 point if correct. You get 0 points for them anyway if you don't get the full score in subtask 2.

The values of n for all tests in subtask 3 are shown in the following table.

The values of n for all tests in subtask 4 are shown in the following table.

5 1
8 5 5 7 7

3
1
1
2
1

5 2
8 5 5 7 7

5
3
2
4
5