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 \leq N \leq 100,000$）。接下来 $N$ 行描述 $A[0] \ldots A[N-1]$，每个都是范围 $0 \ldots 10^9$ 内的整数。输入元素不保证互不相同。

输出格式

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

5
1
5
3
8
2

4

提示

题目来源：Brian Dean

标签: USACO|2018|Silver

来源

USACO|2018|Silver