题目描述

公交车最喜欢冒泡排序了！

他最开始学习到的对一个长度为$\red{N}$的数列的冒泡排序是长这样的：

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

显然伪代码中的"$\red{handsome}$" 的作用只是输出"$\red{handsome}$"，证明公交车非常帅！

但是公交车觉得这段代码的效率有些低，所以他就对上面的冒泡排序进行了部分修改。而修改后冒泡 排序长这样：

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

公交车把这个代码改完后，觉得非常满意，于是他想问你，公交车修改后的代码会输出多少次的 $\red{handsome}$？

输入格式

输入的第一行包含 $\red{(1<=N<=100000)}$接下来$\red{N}$行描述了$\red{A[0]...A[N-1]，}$每个数都是一个 范围为$\red{0...10^9}$的整数。输入数据不保证各不相同。

输出格式

输出"$\red{handsome}$"被输出的次数。

样例

输入样例

5
1
8
5
3
2

输出样例

2