题目描述

工头 Pavel 负责一个施工队，他们正在按照外国建筑师的最新项目建造一座音乐厅。这座建筑的主要特色是主入口处的柱廊，由 $n$ 根柱子组成。与古典建筑观念相反，每根柱子都有自己的高度，并且高度不一定与入口上方屋顶的高度一致。

按照当前计划，从左到右第 $1$ 到第 $n$ 根柱子相对于屋顶平面的高度分别为 $a_1,a_2,\ldots,a_n$ 米。例如，高度为 $10$ 米表示该柱子高出屋顶 $10$ 米；高度为 $-5$ 米表示该柱子顶部与屋顶之间还差 $5$ 米。

在工程交付和音乐厅隆重开幕前三天，建筑师们来到施工现场并修改了项目，提出了一个新的要求：按照欧洲最新时尚，任意两根相邻柱子之间的高度差必须相同。也就是说，对于所有 $1$ 到 $n-1$ 之间的整数 $i$ 和 $j$，都必须满足

每根柱子的具体高度值本身并不重要。由于技术原因，柱子相对于屋顶平面的高度只能是整数米。

将一根柱子的高度向上或向下改变 $x$ 米，都需要花费 $x$ burley。Pavel 请求你帮助他为每根柱子选择新的高度，使得满足上述要求，并且修改高度的总费用尽可能小。请帮助他，否则他以后再也不会被邀请去建造外国项目的建筑了。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 3000000$），表示入口前柱子的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^9 \le a_i \le 10^9$），表示当前柱子的高度。

输出格式

输出两个整数：最优方案中第一根柱子的高度，以及任意两根相邻柱子之间的高度差。

你输出的两个整数的绝对值都不能超过 $10^{16}$。保证存在满足这一条件的最优答案。

样例 1

输入

2
3 -3

输出

3 -6

样例 2

输入

5
3 8 10 13 20

输出

3 4

样例解释

在第一个样例中，不需要改变柱子高度，因为一共只有两根柱子，它们自动满足题目要求。

在第二个样例中，最优的新高度序列为 $3,7,11,15,19$，总修改费用为

评分方式

本题共有 $102$ 个测试，其中两个是样例测试，其余每个测试独立计分，价值 $1$ 分。本题完全 Offline，也就是说你的解答在主测试集上的测试结果会在比赛结束后公布。只有通过全部样例测试的解答，才会被提交到主测试集测试。

保证满足以下附加条件的正确解法至少可以获得对应分数：