P16934 Celestial Balance Array

:::info[Problem Background] The deeper they went, the clearer the ancient magic lingering around them became. It was like invisible currents of water, slowly flowing between the stone walls, the dome, and the corridors. Fern still held her staff and did not fully relax; Stark kept looking back from time to time at the road behind them that was gradually being swallowed by darkness, as if worried that the sounds of the battle just now would draw something else. Only Frieren kept her usual pace, walking forward quietly, as if she had long been used to the feeling of being watched by ancient ruins. After passing through several long and narrow corridors, the three of them arrived in front of a particularly neat hallway. There were no bookshelves on either side of the hallway. Instead, there was a row of black stone pedestals arranged extremely neatly. On each pedestal, a slender crystal was embedded, with faint glimmers of varying brightness flowing across its surface. Those lights were not stable: some were bright, some were dim, and some lightly trembled within a very narrow range, as if responding to each other by some ancient rule. Looking ahead, this entire row of crystals was like a string of stars stretched across the ground, extending all the way to the tightly closed stone door at the end of the hallway. “Another mechanism?” Stark frowned. Frieren stepped forward, lowered her head to look at the spell patterns carved at the base of the pedestal, and nodded gently. “Yes. This is the ‘Celestial Balance Array’ used to keep the passage stable.” She said calmly. “These crystals continuously supply magic to the hallway, but if the fluctuations between different nodes differ too much, the spell will become unstable. If it gets serious, the door ahead will not open either.” Fern carefully looked at the row of crystals and found that the amount of magic contained in each crystal was indeed different. They did not stand out when viewed alone, but once placed together, the uneven fluctuations became especially obvious, like a piece of music with constant ups and downs that could never find true harmony. “Then what should we do?” she asked. Frieren’s gaze slowly swept along the row of crystals, as if confirming their arrangement. “It’s simple.” She said. “Just temporarily seal off a segment of nodes, and let the remaining part regain balance. Ancient mages liked doing this, hiding complicated problems inside very simple appearances.” “To seal off a whole segment? That’s not a small amount of work...” Stark repeated softly, his expression becoming serious. “Yes.” Frieren reached out and lightly touched one of the crystals. A faint ring of light patterns immediately appeared at her fingertips. “But sealing different positions will make the magic fluctuations between the remaining nodes very different. Interesting.” The weak glow in the hallway flowed silently, and the stone door remained tightly closed. :::

There are $n$ “Celestial Balance Arrays” in the hallway, numbered $1 \sim n$. Each “Celestial Balance Array” has a magic value $a_i$. Frieren needs to seal $k$ consecutive “Celestial Balance Arrays”. After sealing, let the remaining unsealed “Celestial Balance Arrays” form a sequence $b$. Define the range of a non-empty sequence as: $$ \max(b)-\min(b) $$ Frieren wants to know, among all valid sealing plans, the maximum possible value and the minimum possible value of the range of sequence $b$.

The first line contains two integers $n, k (1 \leq k < n \leq 2 \times 10^5)$, representing the number of “Celestial Balance Arrays” and the length of the consecutive segment to be sealed. The second line contains $n$ integers $a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^9)$, representing the magic value of the “Celestial Balance Array” with index $i$.

Output one line with two integers, representing the maximum possible range and the minimum possible range under valid sealing plans.

It is not hard to see that if you seal the “Celestial Balance Arrays” with index intervals $[3, 5]$, $[4, 6]$, and $[5, 7]$, the range of the remaining “Celestial Balance Arrays” is $8$ in all cases, and it is not hard to prove that there is no range larger than $8$. If you seal the “Celestial Balance Arrays” with index interval $[1, 3]$, the range of the remaining “Celestial Balance Arrays” is $5$, and it is not hard to prove that there is no range smaller than $5$. :::info[Problem Background] --- As the last seal was completed, the entire hallway suddenly became quiet. The “Celestial Balance Arrays”, which had been flickering with uneven brightness, seemed to finally understand each other’s rhythm, and lit up at the same time with a soft and even light. The spell patterns flowing slowly along the base of the pedestals were also fully illuminated at that exact moment. The dense glow extended along the hallway, and finally poured into the stone door at the end that had remained closed. Then, a deep and ancient rumble slowly sounded from ahead. The sound was not violent, but carried a weight as if it came from extremely distant ages, like a mechanism that had been asleep for too long finally starting to run again. Dust on the surface of the stone door fell in rustling sounds. The patterns engraved on it lit up inch by inch, and then the entire door slowly split open to both sides in front of the three of them. The air sealed behind the door also surged out. There was no expected decay or chill; instead, it carried an unusually quiet, almost solemn feeling. Behind the door was a huge hall soaked in golden radiance. It was not the color of flame, nor the warm light of ordinary crystal lamps. It was more like some ancient brilliance that, after settling for countless years, still had not faded. The high dome, the straight rows of stone pillars, and the layered steps rising in the distance all looked blurry yet sacred in this gold, as if they had not opened an ordinary door, but had accidentally stepped into an old kingdom sealed away. Fern subconsciously held her breath, and even Stark did not speak immediately, which was rare for him. The three of them looked across the empty hall in unison, toward the high platform in the very center. There stood a tall throne quietly, its outline solemn and silent in the golden light. And on the throne, it seemed that something was sitting there. It did not move. There was no sound, and its true appearance could not be seen. It only cast a vague and straight shadow within that overly quiet glow, as if it had been waiting here for a very, very long time. ::: Translated by ChatGPT 5