题目描述

无聊的小美人鱼采集到了很多珍珠，她想把这些珍珠从大到小排成一列。美人鱼在在学校里学过了排序算法，她到目前为止最喜欢的算法是“冒泡排序”。她喜欢陪着冒泡排序一起吐泡泡，这是小美人鱼 对长度为 $N$ 的数组 $A$ 进行排序的代码实现。

sorted = false
while (not sorted):
   sorted = true
   bubble
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

这段代码中的“bubble”指令的作用只是输出“bubble”。

给定一个输入数组，小美人鱼想知道代码会输出多少次“bubble”。

输入格式

输入的第一行包含 $N$（$1 \leq N \leq 100,000$）。接下来 $N$ 行描述了 $A[0] \ldots A[N-1]$，每个数都是一个范围为 $0 \ldots 10^9$ 的整数。输入数据不保证各不相同。

输出格式

输出“bubble”被输出的次数。

样例

输入1

5
1
5
3
8
2

输出1

4

数据范围与提示

对于全部数据保证 $1\le n\le 10^5,0\le a_i\le 10^9$。