题目描述

给出一个$n$个互不相同的非负整数，最初是无序的，现在有两种操作：

选择两个连续的数字，然后反转他们的位置，比如$[1,2]$会变成$[2,1]$

选择三个连续的数字，然后反转他们的位置，比如$[1,2,3]$会变成$[3,2,1]$

可以证明，在有限次以上两种操作下，一定可以将数列变为有序。但是如果一直进行第一种操作，那不就变成冒泡排序了吗，所以你要是最小化第一种操作的次数。

现在问在要把所有的数字变成升序的前提下，最少要进行多少次第一种操作？

输入描述

第一行输入一个正整数$n(1\le n\le 10^5)$，代表数字的个数

接下来$n$行，每行一个整数$a_i(0\le a_i\le 10^9)$,保证这些数字互不相同

输出描述

输出一个整数，代表最少进行的操作$1$的次数

样例

输入

4
2
4
3
1

输出

1

样例解释

先对最后三个数字进行一次操作$2$，然后再对前两个数字进行一次操作$1$