#670. 构造数列

构造数列

样例下载

题目描述

给出一个含有 nn 个元素的数列 AA,让你构造同样含有 nn 个元素的数列 BB,要求:

  • 对于 ∀ 1≤i<j≤n1 ≤ i < j ≤ n,有 Bi≤BjB_i ≤ B_j 或 Bi≥BjB_i ≥ B_j

构造完后,定义 S=∑i=1n∣Ai−Bi∣S = \sum_{i=1}^n |Ai-Bi|。

如何构造,可以使得 S 的值尽可能的小?你只需要输出可以得到的 S 的最小值。

输入格式

第一行:一个整数 nn。

接下来 nn 行:每行一个整数 AiA_i。

输出格式

一个整数,表示答案。

样例输入

7
1
3
2
4
5
3
9

样例输出

3

数据范围

100% 的数据:1≤n≤2⋅1031 ≤ n ≤ 2 · 10^3, 0≤Ai≤1090 ≤ A_i ≤ 10^9