题目描述

求数组中i<j时arr[j]-arr[i]的最大值，归并排序的过程中，每个合并步骤中左半区间的最小值与右半区间的最大值的差（如果左半最小值小于右半最大值），累加到总结果中输出

输入格式

输入两行，第一行n，表示n个数字，第二行输入n个数字

输出格式

输出总计的差值

样例

输入样例 1

5
3 1 4 2 5

输出样例 1

10

输入样例 2

1
5

输出样例 2

0

输入样例 3

3
5 5 5

输出样例 3

0

提示

样例说明：左子区间[3,1,4]差值3（4-1），右子区间[2,5]差值3（5-2）； 合并左右子区间时，左最小值1 < 右最大值5，差值5-1=4； 总差值：3+3+4=10。