冒泡排序的伪代码如下。

f = false
cnt = 0
while (f == false):
   f = true
   cnt++;
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         f = false

给定一个数组，请编程计算出变量 cnt 的值。

第一行读入 N（1 \leq N \leq 100,000）。

接下来 N 行读入 A[0] \ldots A[N-1] ，每个数都是一个范围为 0 \ldots 10^9 的整数。

输入数据不保证各不相同。

输出 cnt 统计的结果。

东方博宜OJ

树状数组离散化