UOJ Logo FLYIOI UOJ

FLYIOI

#34. 冒泡排序(sort)

故事背景

海选的第三关是编程,yuyan阴阴地笑了。

题目描述

冒泡排序算法的运作如下:
1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤,除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
以下是冒泡排序的伪代码:
    void bubbleSort(){
        for i=n-1 to 1
            for j=1 to i
                if a[j]>a[j+1]
                then swap(a[j],a[j+1]);
    }
以下是一个冒泡排序的实例:
    3    2    1    4
    2    3    1    4
    2    1    3    4
    1    2    3    4

我们规定,对于一个1~n的排列,若此数列中两个数 a b在冒泡排序中被交换,则称这两个数为一对交换数。
给出一个1~n的排列,要求在排列中找出尽量多的数,使得其中不存在一对交换数。
以上图为例,有三对交换数,分别是 (2,3)(1,3)(1,2) , 所以最多选出2个数,他们可以是1,4 或 2,4 或 3,4。

输入

第一行一个数n。
第二行n个正整数,表示一个1~n的排列。

输出

一个数,表示能选出的最多的数的个数。

样例输入

4
3 2 1 4

样例输出

2

数据范围

对于30%的数据n<=1000
对于100%的数据 n<=100000