P6481 [CRCI2006-2007] FIREFLY

A Japanese firefly flies into a cave full of obstacles.

There are two kinds of obstacles in the cave: stalagmites (growing upward from the ground) and stalactites (hanging down from the ceiling). The cave is $n$ units long and $h$ units high. From left to right, the first obstacle is a stalagmite; then stalactites and stalagmites appear alternately. The picture below shows an example cave with length $14$ units and height $5$ units:  This Japanese firefly will not avoid obstacles. It only flies at a fixed height. With its superb skills, it can start from one end of the cave and, at some height, break through all obstacles to reach the other end.  For example, in the picture above, if the firefly chooses height $4$ to fly, it will hit a total of $8$ obstacles. But this is not the best choice. Because if it flies at height $1$ or height $5$, it only needs to break through $7$ obstacles. To reduce the pain, you need to help the firefly find the minimum number of obstacles it must destroy, and how many different heights achieve this minimum.

The first line contains two integers $n, h$, representing the length and height of the cave. The testdata guarantees that $n$ is even. The next $n$ lines each contain one integer, representing the length of an obstacle. It is guaranteed that all obstacle lengths are less than $h$.

Output one line with two integers: the minimum number of obstacles that must be destroyed, and the number of different height choices that achieve this minimum.

#### Constraints For $100\%$ of the testdata, it is guaranteed that $2 \le n \le 2 \times 10^5$ and $2 \le h \le 5 \times 10^5$. #### Notes **Translated from [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [Regional Competition](https://hsin.hr/coci/archive/2006_2007/regional_tasks.pdf) *T3 FIREFLY***。 Translated by ChatGPT 5