波西·杰克逊与奥林匹斯众神

题目描述

在宙斯的闪电被盗这一事件发生之前，波西当然需要先了解自己的身世、奥林匹斯众神的事，以及古希腊诸神和怪物真实存在于现实世界。

波西第一次知道奥林匹斯众神，是从他小时候得到的一本书中。书里有一幅插图，所有 $n$ 位神祇排成一排，下方标注了第 $i$ 位神的实力为 $a_i$。我们定义这一排的不和谐度为相邻神祇实力差的最大绝对值，即

$$ D = \max_{i=1}^{n-1} |a_i - a_{i+1}|. $$

现在，波西对神祇和其他生物有了更深的了解，他确信书中有一个印刷错误。考虑到这是一本严肃的书，错误只能有一处，并且波西认为，如果改正这个错误（即修改某一个 $a_i$ 为另一个整数），不和谐度 $D$ 可以达到可能的最小值。

请帮助波西确定应该修改哪个 $a_i$，才能使得奥林匹斯众神排成一排的不和谐度最小。

输入格式

第一行包含一个整数 $n$ ——书中插图上奥林匹斯众神的数量（$2 \le n \le 5 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_i$ ——书中所列神祇的实力值（$1 \le a_i \le 10^9$）。

输出格式

输出三个整数，空格隔开：$D_\mathrm{min}$、$i$ 和 $a_i^*$ ——可以达到的最小不和谐度，以及需要修改实力值的神祇编号（从 1 开始）和修改后的实力值。

如果存在多个解，输出任意一个即可。特别地，如果 $D_\mathrm{min}$ 与初始值 $D$ 相等，可以输出任意 $i$ 且 $a_i^* = a_i$，即认为书中没有印刷错误。

评分系统

每个子任务的分数仅当该子任务及所有必要子任务的所有测试点均通过时才会获得。

样例

样例输入 1

5
4 1 3 5 4

样例输出 1

2 2 3

样例输入 2

4
1 2 1 1

样例输出 2

0 2 1