题目描述

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

她到目前为止最喜欢的算法是冒泡排序。这是 Bessie 的对长度为 $n$ 的数组 $a$ 进行排序的奶牛码实现。

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

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

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

输入格式

输入的第一行包含 $n(1 \leq n \leq 10^5)$。

接下来 $n$ 行描述了 $a_0 \ldots a_{n-1}$，每个数都是一个范围为 $0 \ldots 10^9$ 的整数。输入数据不保证各不相同。

输出格式

输出moo被输出的次数。

5
1
5
3
8
2

4