AT_agc003_c.[AGC003C] BBuBBBlesort!

高桥君在生日时收到了一个长度为 $N$ 的数列。第 $i$ 个元素是整数 $A_i$。任意两个元素都互不相同。高桥君想要将这个数列重新排列成单调递增的顺序。

高桥君拥有超能力，可以在任意时刻进行以下两种操作：

• 操作 $1$：选择数列中连续的两个元素，交换它们的顺序。
• 操作 $2$：选择数列中连续的三个元素，反转这三个元素的顺序。

高桥君喜欢操作 $2$，但不喜欢操作 $1$。请你求出，在使用这两种操作将数列变为单调递增时，操作 $1$ 的最小次数。

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出操作 $1$ 的最小次数。

限制条件

• $1 \leq N \leq 10^5$
• $0 \leq A_i \leq 10^9$
• 如果 $i \neq j$，则 $A_i \neq A_j$
• 所有输入均为整数。

样例解释 1

可以通过如下操作将数列变为单调递增：

• 首先，将最后三个元素反转，数列变为 $2,1,3,4$。
• 然后，将前两个元素交换，数列变为 $1,2,3,4$。

在这个操作序列中，连续两个元素交换的操作次数为 $1$。无法通过更少的操作 $1$ 次数得到单调递增的数列，因此输出 $1$。

由 ChatGPT 4.1 翻译