Torty the sea turtle is fending off invading jellyfish!
Torty has an army of $$$n$$$ turtles standing in a line, each holding a shield of length $$$\ell$$$. Initially, the shield of the $$$i$$$-th turtle is at the interval $$$[x_i, x_i + \ell)$$$. Torty wants the turtles to arrange their defense positions so that their shields concatenate into a contiguous interval of length $$$n\cdot\ell$$$ inside the battle interval $$$[0, b)$$$.
Turtles are serene creatures. They would rather bask in the sun than move around. But once moving, they can go any distance. What is the minimum number of turtles that have to move to form the target configuration?
Torty entrusts this important problem to you. Solve it quickly!
The first line contains three integers $$$n$$$, $$$\ell$$$, and $$$b$$$, where $$$1 \le n \le 2\cdot 10^5$$$, $$$1 \le \ell, b \le 10^9$$$, and $$$n\cdot\ell \le b$$$. The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$, where $$$-10^9 \le x_i \le 10^9$$$. The shields may overlap at their initial positions.
Print the minimum number of turtles that have to move.
6 2 13 -1 3 4 5 12 11
3
10 77510323 901306288 620843873 233292258 698354196 310802581 761289 155781935 465823227 388312904 78271612 543333550
0
10 22312461 336063920 332343265 290626439 150730813 173043274 148781733 83793430 171756290 65988290 158227842 170597107
7
The best way is to move the turtle with shield at $$$[-1, 1)$$$ to $$$[1, 3)$$$, the turtle with shield at $$$[4, 6)$$$ to $$$[7, 9)$$$, and the turtle with shield at $$$[12, 14)$$$ to $$$[9, 11)$$$. Then all shields are joined into a contiguous interval $$$[1, 13)$$$ inside the battle interval $$$[0, 13)$$$.
Blue Puppy is looking for his little brother Torty. It's time to go home, but Torty is still playing among sea turtles and jellyfish on the beach, which is an interval $$$[0, b)$$$.
Blue Puppy has $$$n$$$ UFOs hovering above the beach, where the $$$i$$$-th UFO covers an interval $$$[x_i, x_i + \ell)$$$ with surveillance cameras.
What is the minimum number of UFOs that have to move so that the $$$n$$$ UFOs together cover the whole length of the beach?
The first line contains three integers $$$n$$$, $$$\ell$$$, and $$$b$$$, where $$$1 \le n \le 10^5$$$, $$$1 \le \ell, b \le 10^9$$$, and $$$n\cdot\ell \ge b$$$. The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$, where $$$-10^9 \le x_i \le 10^9$$$. The intervals covered by the UFOs may overlap at their initial positions.
Print the minimum number of UFOs that have to move.
8 2 10 -1 -2 3 4 5 8 9 10
2
10 77510323 144050237 37352276 91207595 287623234 -48741332 272918498 233298117 162635825 18573522 -73431711 177103533
0
10 22312461 199036869 55220051 138331995 182876693 25339421 21654390 110080598 101291658 117659246 121368663 181018092
5
One of the best ways is to move the UFO at $$$[4, 6)$$$ to $$$[1, 3)$$$, and move the UFO at $$$[10, 12)$$$ to $$$[6, 8)$$$. Then the $$$8$$$ UFOs together cover the interval $$$[-2, 11)$$$, which contains the beach $$$[0, 10)$$$.