题目描述

乐乐开始在不同的在线编程网站上学习算法，留意着竞赛之外的长期职业生涯的可能性。

他到目前为止最喜欢的算法是 “冒泡排序”。这是乐乐对长度为 $N$ 的数组 $A$ 进行排序的猫猫码实现。

sorted = false
while (not sorted):
   sorted = true
   miao
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

显然，猫猫码中的 miao 指令的作用只是输出 miao。奇怪的是，乐乐看上去执着于在他的代码中的不同位置使用这个语句。

给定一个输入数组，请预测乐乐的代码会输出多少次 miao。

输入文件 sort.in

输入的第一行包含 $N$。接下来 $N$ 个整数描述了 $A[0] \sim A[N−1]$。输入数据不保证各不相同。

输出文件 sort.out

输出 miao 被输出的次数。

5
1 5 3 8 2

4

10
64 11 76 89 41 96 90 20 61 32

8

提示

对于 $30\%$ 的数据，$N \le 5000$。

对于 $100\%$ 的数据，$1≤N≤10^5$，$0 \le A[i]\le 10^9$。