1304. [HAOI 2006]数字序列

【题目描述】

现在我们有一个长度为 $n$ 的整数序列 $A$.但是它太不好看了,于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。

【输入格式】

第一行包括一个整数 $n$ ，接下来 $n$ 个整数按顺序描述每一项的键值。

【输出格式】

第一行一个整数，表示最少需要改变多少个数。

第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。

【样例输入1】

4
5 2 3 5

【样例输出1】

1
4

【样例输入2】

5
1 234 5 67 8

【样例输出2】

2
290

【样例输入3】

10
31016 27317 22103 39750 17668 20366 2005 9690 16554 42284

【样例输出3】

6
146211

【数据规模与约定】

对于 $70\%$ 的数据，保证 $n ≤ 10^3$;

对于 $100\%$ 的数据，保证 $1≤n≤5×10^5，1≤a_i≤10^5$。

数据保证 $a_i$ 随机生成。