Problem F
Antenna Analysis
Åke has heard that there may be some suspicious 5G radiation in his city. To test this, he uses the antenna on his roof to measure the 5G level each day. However, he does not know how he should analyze the data.
We are given the measurements for $n$ consecutive days as a list of numbers $x_1, \ldots , x_ n$ (where $x_ i$ denotes the measurement for day $i$) and a constant $c$ that measures how much Åke expects the radiation to vary from day to day. We want to find, for each day $i$, the most significant difference between the measurement on day $i$ and any earlier day, after the expected variations are taken into account. More precisely, the goal is to find the maximum value of
\[ |x_ i-x_ j| - c \cdot |i-j| \]where $j \le i$. I.e., we want to find a large difference in 5G level that has happened recently.
Input
The first line of input contains the two integers $n$ and $c$ ($1 \le n \le 4 \cdot 10^5$, $1 \le c \le 10^6$), the number of measurements and expected day-to-day variation. The second input line contains the $n$ integers $x_1,x_2,\dots ,x_ n$ ($1 \le x_ i \le 10^6$ for $i=1,2,\dots ,n$), giving the measurements of the $n$ days.
Output
Output $n$ integers $y_1, \ldots , y_ n$, where $y_ i$ is the most significant difference on day $i$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 2 7 1 5 4 |
0 4 5 3 1 |
