[USACO18OPEN]Out of Sorts S

题目描述

留意着农场之外的长期职业生涯的可能性,奶牛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 100,000$)。接下来$N$行描述了$A[0] \ldots A[N-1]$,每个数都是一个范围为$0 \ldots 10^9$的整数。输入数据不保证各不相同。

输出格式


输出“moo”被输出的次数。

输入输出样例

输入样例 #1

5
1
5
3
8
2

输出样例 #1

4

说明

供题:Brian Dean