| Codeforces Round 1134 (Div. 4) |
|---|
| Finished |
This is the hard version of the problem. The two versions differ only in the constraints on $$$n$$$, on the sum of $$$n$$$ over all test cases, and on the number of test cases.
A circular trail around a lake consists of $$$n$$$ sections numbered from $$$1$$$ to $$$n$$$ along the trail. The height of the $$$i$$$-th section is $$$h_i$$$. Sections $$$i$$$ and $$$i+1$$$ are adjacent for each $$$i$$$ from $$$1$$$ to $$$n-1$$$, and sections $$$n$$$ and $$$1$$$ are adjacent as well.
The steepness of the trail is the maximum absolute difference between the heights of two adjacent sections. In other words, the steepness is $$$\max_{1 \le i \le n} \left|h_i - h_{i+1}\right|$$$, where $$$h_{n+1}$$$ should be considered to exist and to be equal to $$$h_1$$$.
You have $$$k$$$ units of soil. One unit of soil increases the height of one section by $$$1$$$; several units may be used on the same section. Soil cannot be removed, so the heights can only increase.
Find the minimum possible steepness of the trail after using at most $$$k$$$ units of soil.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 10^6$$$, $$$0 \le k \le 10^{18}$$$) — the number of sections and the number of units of soil.
The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — the heights of the sections.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print a single integer — the minimum possible steepness of the trail after using at most $$$k$$$ units of soil.
64 31 5 2 85 52 9 4 1 63 01 4 73 1001 10 15 54 1 1 1 16 143 6 2 4 1 5
546021
In the first test case, you can use two units of soil on section $$$1$$$ and one unit on section $$$3$$$. The heights become $$$3, 5, 3, 8$$$, and the differences between adjacent sections are $$$2$$$, $$$2$$$, $$$5$$$, and $$$5$$$, the last one being between sections $$$4$$$ and $$$1$$$. So the steepness is $$$5$$$.

The ring is divided into four sections of the trail, with heights shown inside them. The $$$\Delta$$$ labels at the boundaries show the absolute differences between adjacent heights, and $$$+2$$$ and $$$+1$$$ show the added soil.
Steepness $$$4$$$ cannot be achieved: the height of section $$$4$$$ is at least $$$8$$$, and sections $$$3$$$ and $$$1$$$ are adjacent to it, so both of them would have to be raised to at least $$$4$$$, which needs $$$2 + 3 = 5$$$ units of soil.
In the second test case, the heights can become $$$5, 9, 5, 2, 6$$$ using $$$3 + 1 + 1 = 5$$$ units of soil, and the steepness becomes $$$4$$$. Steepness $$$3$$$ cannot be achieved: the height of section $$$2$$$ is at least $$$9$$$, so sections $$$1$$$ and $$$3$$$ would have to be raised to at least $$$6$$$, which needs $$$4 + 2 = 6$$$ units of soil.
In the third test case, no soil can be used. Sections $$$3$$$ and $$$1$$$ are adjacent, so the steepness is $$$7 - 1 = 6$$$.
In the fourth test case, all heights can be made equal to $$$10$$$ using $$$18$$$ units of soil.
In the fifth test case, the heights can become $$$4, 2, 1, 1, 2$$$ using $$$1 + 1 = 2$$$ units of soil, and the steepness becomes $$$2$$$. Steepness $$$1$$$ cannot be achieved: the height of section $$$1$$$ is at least $$$4$$$, and sections $$$2$$$ and $$$5$$$ are adjacent to it, so they would have to be raised to at least $$$3$$$, and then sections $$$3$$$ and $$$4$$$ to at least $$$2$$$, which needs $$$2 + 1 + 1 + 2 = 6$$$ units of soil.
| Name |
|---|


