题目描述

Snuke 从他的母亲那里收到了一个长度为 $N$ 的整数序列，作为生日礼物。序列的第 $i$（$1 ≦ i ≦ N$）个元素是 $a_i$。元素两两不相同。他正在按照递增顺序对该序列进行排序。借助神奇的力量，他可以按照以下两种操作之一对序列进行任意次操作：

• 操作 $1$：选择 $2$ 个相邻的元素，然后颠倒这两个元素的顺序。
• 操作 $2$：选择 $3$ 个连续的元素，然后颠倒这三个元素的顺序。

Snuke 喜欢操作 $2$，但不喜欢操作 $1$。找出他必须执行的最小操作 $1$ 的次数，以便将序列排序为递增顺序。

约束条件

• $1 ≦ N ≦ 10^5$
• $0 ≦ A_i ≦ 10^9$
• 如果 $i ≠ j$，则 $A_i ≠ A_j$。
• 所有输入值都是整数。

输入

从标准输入中以以下格式给出输入：

$N$
$A_1$
:
$A_N$

输出

输出 Snuke 必须执行的 Operation $1$ 的最小次数。

样例输入 1

4
2
4
3
1

样例输出 1

1

给定序列可以按以下方式排序：

• 首先，颠倒最后三个元素的顺序。序列变为：$2,1,3,4$。
• 然后，颠倒前两个元素的顺序。序列变为：$1,2,3,4$。

在这个操作序列中，执行了一次操作 $1$。不能通过更少的操作 $1$ 来对序列排序，因此答案是 $1$。

样例输入 2

5
10
8
5
3
2

样例输出 2

0