20452번 - Робомарафон 서브태스크점수다국어

В робомарафоне принимают участие $n$ роботов. Роботы должны преодолеть одинаковую дистанцию, передвигаясь по расположенным рядом друг с другом дорожкам шириной один метр каждая. Известно, что расположенный на $i$-й дорожке робот преодолевает дистанцию за $a_i$ секунд. 

В точке старта каждого робота установлено специальное сигнальное устройство, которое должно сработать в момент старта. Чтобы сделать соревнования менее предсказуемыми, судьи перед стартом могут отключить некоторые сигнальные устройства, остальные устройства останутся активными. Только активные устройства срабатывают в тот момент, когда главный судья начинает робомарафон. В начале робомарафона хотя бы одно сигнальное устройство должно являться активным.

Каждый робот начинает движение в тот момент, когда до него доходит стартовый сигнал от активного устройства. Сигнал распространяется со скоростью 1 метр в секунду. Если ближайшее к $i$-му роботу активное устройство находится на $j$-й дорожке, то расстояние между ними составляет $x_i=|i-j|$ метров. Этот робот начнёт движение через $x_i$ секунд после старта, преодолеет дистанцию за $a_i$ секунд, и финиширует через $f_i = a_i + x_i$ секунд после старта робомарафона.

Пусть $k_i$ --- количество роботов, которые финишировали строго раньше $i$-го робота. Место $i$-го робота по итогам робомарафона равно $k_i + 1$. Если несколько роботов финишируют одновременно, а перед ними финишировали $k$ роботов, то считается, что все они заняли $(k+1)$-е место.

Рассмотрим пример. Пусть $n = 3$, роботы преодолевают дистанцию за $a_1 =2$, $a_2 = 3$ и $a_3 = 5$ миллисекунд, а активным являлось только сигнальное устройство у третьего робота. Тогда первый робот начнет движение через $2$ секунды после начала забега, $f_1 = 4$. Второй робот начнет движение через $1$ секунду, $f_2 =4$. Третий робот начнет движение в момент старта, $f_3 = 5$. По итогам забега первый и второй робот делят первое место, третий робот занимает третье место. Если же, например, сработают все три сигнальных устройства, роботы финишируеют через $f_1 = 2$, $f_2 = 3$, $f_3 = 5$, секунд, соответственно. Первый робот займет первое место, второй робот займет второе место, а третий робот --- третье место.

Как видно из примера, место, которое займет робот, зависит от того, какие сигнальные устройства являются активными. Необходимо обрабатывать два типа запросов:

1. для каждого робота определить минимальное место, которое он может занять;
2. для каждого робота определить максимальное место, которое он может занять.

Требуется написать программу, которая по типу запроса и информации о времени прохождения дистанции каждым роботом определяет для каждого робота минимальное или максимальное место, которое он может занять в марафоне.

В первой строке входных данных находятся два целых числа: $n$ --- количество роботов ($1 \le n \le 200\,000$), и $p$ --- тип запроса. Значение $p = 1$ означает, что для каждого робота необходимо определить минимальное место, которое он может занять, значение $p = 2$ означает, что для каждого робота необходимо определить максимальное место, которое он может занять.

Во второй строке находятся $n$ целых чисел $a_1, a_2, \ldots, a_n$ --- время, за которое роботы преодолевают дистанцию ($0 < a_i \le 10^9$).

Требуется вывести $n$ целых чисел, $i$-е из которых, в зависимости от типа запроса, должно задавать минимальное или максимальное место, которое может занять $i$-й робот.