P6481.md

[COCI2006-2007] FIREFLY

题目描述

山洞中有两种障碍物：石笋（从地面向上生长）和钟乳石（从洞顶垂挂下来）。山洞长 $n$ 个单位，高 $h$ 个单位。从左到右第一个障碍物是石笋；紧接着钟乳石与石笋依次交替出现。

下图是一个长 $14$ 个单位，高 $5$ 个单位的山洞示例：

这只日本萤火虫并不会绕开障碍物，而只会沿着同一高度飞行。凭借着自己精湛的功夫，他会从山洞的一端，以某一高度撞开所有障碍物而达到另一端。

例如在上图中，如果萤火虫选择高度 $4$ 来飞行，那么它总共会撞到 $8$ 个障碍物。

但这并不是最好的选择。因为如果它选择高度 $1$ 或高度 $5$ 飞行的话，只需要撞开 $7$ 个障碍物就行了。

为了减轻疼痛，你需要帮助萤火虫找出最少需要摧毁的障碍的数量和摧毁最少障碍物的高度种类数。

输入格式

输入第一行两个整数 $n,h$，表示山洞的长度和高度。数据保证 $n$ 是偶数。

接下来的 $n$ 行，每行一个整数，表示障碍物的长度。保证所有障碍物的长度都小于 $h$。

输出格式

输出一行两个整数，分别为最少需要摧毁的障碍物数量和摧毁最少的障碍物有多少种高度的选择。

样例 #1

样例输入 #1

6 7
1
5
3
3
5
1

样例输出 #1

2 3

样例 #2

样例输入 #2

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

样例输出 #2

7 2

提示

数据规模与约定

对于 $100%$ 的数据，保证 $2\le n\le 2\times 10^5$，$2\le h\le 5\times 10^5$。

说明

题目译自 COCI2006-2007 Regional Competition T3 FIREFLY。