Description

小码哥有 n 个手下,他们的编号为「1,n]。小码哥想要给他们发放工资，用一个长度为n 的数列， a[i]表示编号为i的手下初始收到的工资，但发工资时没有计算好，导致每个人到手的工资不一样，为了使他们的工资相同，现在小码哥可以使得编号在区间 [l,r]中的手下，收到1或上交1的工资。即工资+1或工资-1;

求至少需要多少次操作才能使所有人的工资相同都一样?

工资可以暂时为负数，小码哥可以压榨他的手下，让手下暂时垫付部分钱，之后再还;小码哥也可以多付一些钱给手下，也可以少给一些(自己贪污一点)，即工资总数不要求一定是初始手下的工资之和。只要他们每个人的工资一样就可以。

Input Format

第一行一个正整数 n;

接下来几行，每行一个整数，第i+1 行的正整数表示 a[i]。

Output Format

第一行输出最少操作次数。

4
3
2
3
4

2

Hint

1<n<100000,0<ai<10000000

Source

信奥星OJ http://127.0.0.1