Description

The fence is made of $n$ wooden boards. Each board is $1$ cm wide, and the heights are not necessarily the same. To paint faster, he bought a super paint roller that is $x$ cm wide. However, the super roller has a catch: Matija must always keep the roller in full, tight contact with the boards; otherwise, paint will drip around and stain everything. Also, the roller must always stay parallel to the ground to prevent leaking. This means that, to use the roller safely, Matija needs to choose $x$ boards and paint them in one pass from the bottom of the shortest board up to its top. Then he chooses some other boards and paints them, and so on.

As a result, some parts of some boards will not be painted. Matija has to paint those parts with a toothbrush. This is obviously quite boring, so he asks you to write a program that finds the minimum area he must paint by hand. Since there is more than one way to do this, he also wants to know the minimum number of times the super roller needs to be used.

Input Format

The input has two lines.

The first line contains two integers $n,x$, representing the number of boards and the width of the super paint roller.
The second line contains $n$ positive integers $h_1,h_2,\dots,h_n$, where $h_i$ is the height of the $i$-th board.

Output Format

The output has two lines.

The first line contains one integer, the minimum area that Matija must paint by hand.
The second line contains one integer, under the condition that the hand-painted area is minimized, the minimum number of times the super roller must be used.

5 3
5 3 4 4 5

3
2

10 3
3 3 3 3 3 3 3 3 3 3

0
4

7 4
1 2 3 4 3 2 1

4
4

Hint

Sample 1 Explanation

For sample $1$, Matija needs to use the super roller twice.

• First time, use the super roller to paint boards $1,2,3$ with a painted height of $3\text{ cm}$, so the painted area is $9\text{ cm}^2$.
• Second time, use the super roller to paint boards $3,4,5$ with a painted height of $4\text{ cm}$, so the painted area is $12\text{ cm}^2$.

Because the two paintings overlap by $3\text{ cm}^2$, the remaining area that needs to be painted by hand is $5+3+4+4+5-9-12+3=3\text{ cm}^2$. It can be proven that this plan makes the hand-painted area minimal, and the number of super-roller uses is also minimal.

You can understand it better with the figure below:

Constraints

For all testdata, $1\leqslant n\leqslant 10^6$, $1\leqslant x\leqslant 10^5$, $1\leqslant h_i<10^6$.

Source

This problem is from COCI 2009-2010 CONTEST 4 T4 OGRADA, using the original testdata configuration, with a full score of $100$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5