3043. [USACO Open18 Silver]Out of Sorts

【题目描述】

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

【输出格式】

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

【样例输入】

5
1
5
3
8
2

【样例输出】

4

【数据规模】

$40$%的数据$N<=10000$;
$60$%的数据$N<=100000$;
$80$%的数据大小顺序时混乱的;

【来源】

USACO 2018 OPEN CONTEST Silver Problem 1

供题：Brian Dean