You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

忐忑楼梯有N块台阶，每块台阶都可以上下移动，一开始都有各自的高度，我们的目标是将各台阶的高度调整为相同。你可以发送一系列的指令控制这个楼梯，每条指令可以将第L个到第R个整个区间所有台阶升高1个高度或者降低一个高度。问至少需要多少条指令才能将所有台阶调整到同一高度？

输入格式

第一行，一个整数N。

第二行，N个整数，表示从左往右的各台阶的原来的高度。

输出格式

一个整数，表示将所有台阶调整到同一高度的最少指令数。

输入样例

5

1 2 2 3 1

输出样例

2

数据范围

1<=N<=100000

提示说明

若L==R，表示这个区间中只有一个台阶。