故事背景

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

题目描述

冒泡排序算法的运作如下：

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