[HAOI2006]数字序列

给定一个长度为 $n$ 的整数序列 $A$。现在需要修改其中的一些数，使整个序列变为严格单调递增序列。

你希望修改的数尽可能少；在修改数量最少的前提下，还希望所有数的改变量绝对值之和最小。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，依次表示 $A_1,A_2,\ldots,A_n$。

输出格式

第一行输出一个整数，表示最少需要修改的数的数量。

第二行输出一个整数，表示在修改数量最少的前提下，所有数的改变量绝对值之和的最小值。

样例输入

4
5 2 3 5

样例输出

1
4

数据范围

• $1\le n\le 35000$；
• $1\le A_i\le 10^9$；
• 测试数据中的各个 $A_i$ 相互独立，并在 $[1,10^9]$ 内均匀随机生成；
• 本题的时间复杂度按照上述随机模型下的期望复杂度计算。

来源与许可

本题为 HAOI 2006 试题「数字序列」，题面与测试数据整理自 BZOJ。

样例 1

输入

4
5 2 3 5

输出

1
4