问题 C: 有序序列

问题 C: 有序序列

时间限制: 1 Sec  内存限制: 256 MB
提交: 13  解决: 3
[提交][状态][讨论版][命题人:]

题目描述

给定一个长度为 n的数列 a1,a2,…,an每次可以选择一个区间 [l,r]使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使这个序列变为有序序列。有序序列是指序列要么是一个非升序列。要么是一个非降序列。

输入

第一行输入正整数 nn

接下来 nn 行,每行输入一个整数,第 i+1i+1 行的整数代表 aiai

输出

一行输出最少操作次数。


样例输入

4
10
10
11
1

样例输出

1

提示


1<=n<=10^6



0<=ai<=10^9



样例解释:可以把11减去1,使序列变为 10 10 10 1  成为非升序列

[提交][状态]