星图的最长静默

题目描述

观星台将夜空中的亮点按 1 到 n 编上编号，记录下“异常稳定的亮点”作为关键锚点。两颗相邻锚点编号之间的差值，称为一次“静默时段”的长度。天文学家想知道，在 1 到 n 的编号中，最长的一段“静默时段”有多长，以及它对应的两颗锚点编号。如果有多个相同的“静默时段”，取锚点最小的。

请你帮他们找出答案。

输入格式

输入仅一行，一个整数 n。

输出格式

输出一行三个整数：a b d，分别表示最长静默时段两端的锚点编号 a 与 b（满足 a < b），以及时段长度 d = b - a。若在 1 到 n 内锚点数量不足两颗，则输出 0 0 0。

输入输出样例 #1

输入 #1

30

输出 #1

23 29 6

说明/提示

• 可将“异常稳定的亮点”理解为在大于 1 的自然数中，只能被 1 和自身整除的编号。
• 对于 100% 的数据，2 <= n <= 1e7。建议先确定所有锚点，再线性扫描得到最长静默时段。