冒泡计数器（Bubble）

题目背景

杨乐多学会了带 提前结束优化 的冒泡排序后，发现它并不一定要跑满 $n$ 轮：当某一轮没有发生交换时，排序就结束了。
他想知道：对于一个给定的排列，冒泡排序到底会执行多少轮外层循环？

题目描述

给定一个由 $1 \sim n$ 组成的排列 $a_1,a_2,\dots,a_n$ 。杨乐多运行如下 优化冒泡排序（下标从 $1$ 开始）：

• 外层轮数 $i = 1,2,\dots$
• 每一轮从左到右比较相邻元素 $(a_j, a_{j+1})$，若 $a_j>a_{j+1}$ 则交换。
• 若某一轮没有发生任何交换，则立即结束，并输出本轮的轮数 $i$ 。

伪代码如下：

for i = 1..n:
    swapped = false
    for j = 1..n-i:
        if a[j] > a[j+1]:
            swap(a[j], a[j+1])
            swapped = true
    if swapped == false:
        print(i)
        break

输入格式

第一行一个整数 $n$ 。
第二行 $n$ 个整数，表示排列 $a_1,a_2,\dots,a_n$ 。

输出格式

输出一个整数，表示该优化冒泡排序停止时的轮数。

输入输出样例

样例输入 1

3
3 2 1

样例输出 1

3

样例解释 1

• 第 $1$ 轮后：$3$ 被一路 冒 到末尾，序列变为 $[2,1,3]$
• 第 $2$ 轮后：变为 $[1,2,3]$
• 第 $3$ 轮：无交换，停止输出 $3$

样例输入 2

5
1 2 3 4 5

样例输出 2

1

样例解释 2

• 第 $1$ 轮就没有交换，直接停止。

数据范围与提示

对于 $100\%$ 的数据，保证 $1 \le n \le 2\times 10^5$