seuOJ396 - 谱面改造

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：春季, 夏季, 校赛, 2022

题目描述

Lawseria 早就看 Thor0 不顺眼了，而明天他终于将在下落式音乐游戏 Manialody 中挑战 Thor0。

在游戏 Manialody 中，玩家需要根据音乐，在合适的时机点击按键。Manialody 一共有 $n$ 个轨道，每个按键都摆放在轨道中。玩家们根据按键在轨道中的排列形式，对于谱面进行分类，其中常见的类别包括“乱键”与“纵连”等。

上图为 $n=4$ 时对于“乱键”与“纵连”的示例。在上图的选段中，虽然两者的时间长度与按键数相同（均在 $9$ 单位时间内有 $14$ 个按键），但可以很明显的看出“纵连”对于点击速度的要求更高、而“乱键”更考验玩家的协调能力。不同的玩家对于不同类别的按键排列擅长程度不同，比如 Lawseria 被称为“乱键天王”、而 Thor0 则是远近闻名的“纵连皇帝”。

在比试的前一天，Lawseria 收到了所有比赛谱面并进行练习。在这个过程中，他惊讶地发现谱面中有很多“纵连”，而“乱键”则几乎不存在。于是他决定对于谱面进行改造，并将改造后的谱面提交给裁判。

Lawseria 希望能在不改变每个按键点击时间的情况下，通过调整按键的轨道分布来将谱面改造为“乱键”。为了方便起见，他选择“同一轨道内相邻两次点击的时间间隔的最小值” $min\_gap$ 作为评价标准，在这个标准下，“乱键”的 $min\_gap$ 应尽量大。比如在上面的示例中，“乱键”的 $min\_gap$ 等于 $2$，而“纵连”的 $min\_gap$ 等于 $1$。

时间紧迫，Lawseria 不得不求助于你，请你帮助他计算最大的可行 $min\_gap$。

输入格式

第一行包含两个整数 $n, m$（$1\leq n < m\leq 1\times 10^5$），分别表示轨道数与按键数。

接下来一行包含 $m$ 个整数 $t_i$ （$1\leq t_i\leq 1\times 10^9$），其中 $t_i$ 表示第 $i$ 个按键的出现时间。$t_i$ 不一定互不相同，但数据保证等于某一特定值的 $t_i$ 数量不超过 $n$，即 $max\{\sum_i^m (t_i==specific\_value), 1\leq specific\_value\leq 10^9\}\leq n$。

输出格式

输出一个整数 $min\_gap$，其含义在题面中已解释。

样例

样例输入1

4 14
1 1 2 3 3 4 5 5 6 7 7 8 9 9

样例输出1

2

样例输入2

3 6
1 2 1 2 1 2

样例输出2

1

样例解释

对于测试用例1，题面图片中的“乱键”片段是一种合法的改造方式。