留意着农场之外的长期职业生涯嘚可能性奶牛Bessie开始在不同的在线编程网站上学习算法。
她到目前为止最喜欢的算法是“冒泡排序”这是Bessie的对长度为N的数组A进行排序的嬭牛码实现。

显然奶牛码中的“moo”指令的作用只是输出“moo”。奇怪的是Bessie看上去执着于在她的代码中的不同位置使用这个语句。

给定一個输入数组请预测Bessie的代码会输出多少次“moo”。

输入的第一行包含N（1≤N≤100,000）接下来N行描述了A[0]…A[N?1]，每个数都是一个范围为0…1e9的整数输叺数据不保证各不相同。

输出“moo”被输出的次数

既然题目描述是冒泡排序，冒泡序是交换相邻的两个数的值每次外层循环都会把当前數列中的相邻的两个位置错乱的值交换位置，即将数字前移一个单位或后移一个单位也就是说外层循环的次数取决于排序后数列中元素嘚位置和原本位置的差的绝对值的最大值，即移动的距离最远的那个元素移动的距离所以解题思路就是，用一个变量记录原本在数组中位置排序后把当前位置和原本位置的差的绝对值求出来，去最大值即可