Problem2657--附加题:冒泡排序-排序的轮数

2657: 附加题:冒泡排序-排序的轮数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 143  Solved: 69
[Status] [Submit] [Creator:]

Description

使用冒泡排序给一个包含 n 个整数的数列排序,每一轮从左往右依次比较相邻元素,最多需要 n-1 轮就能够实现排序。

但是有可能不用 n-1 轮就能够实现排序。比如,对数列 [3, 2, 1, 6, 5, 4] 进行从小到大排序:  

- 第 1 轮操作后数列变为 [2, 1, 3, 5, 4, 6];
- 第 2 轮操作后数列变为 [1, 2, 3, 4, 5, 6]。

只需要 2 轮操作就实现了从小到大排序了。

现在给你一个长度为 n 的数列,问:使用冒泡排序,至少需要几轮操作能够将这个从小到大排序?

Input

第一行,一个整数 n(2 ≤ n ≤ 1000),表示数列大小。  

第二行,n 个整数,两两之间以一个空格分隔,表示这个数列中的每个元素。

Output

输出一个整数,表示使用冒泡排序对这个数列进行从小到大排序,至少需要几轮操作。  

如果这个数列一开始就是从小到大排好序的,那么你输出的整数应为 0。

Sample Input Copy

6
3 2 1 6 5 4

Sample Output Copy

2

Source/Category