Score : $600$ points

Problem Statement

Snuke got an integer sequence of length $N$ from his mother, as a birthday present. The $i$-th $(1 \leq i \leq N)$ element of the sequence is $a_i$. The elements are pairwise distinct. He is sorting this sequence in increasing order. With supernatural power, he can perform the following two operations on the sequence in any order:

• Operation $1$: choose $2$ consecutive elements, then reverse the order of those elements.
• Operation $2$: choose $3$ consecutive elements, then reverse the order of those elements.

Snuke likes Operation $2$, but not Operation $1$. Find the minimum number of Operation $1$ that he has to perform in order to sort the sequence in increasing order.

Constraints

• $1 \leq N \leq 10^5$
• $0 \leq A_i \leq 10^9$
• If $i \neq j$, then $A_i \neq A_j$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$A_1$

:

$A_N$

Output

Print the minimum number of times Operation $1$ that Snuke has to perform.

4
2
4
3
1

1

The given sequence can be sorted as follows:

• First, reverse the order of the last three elements. The sequence is now: $2,1,3,4$.
• Then, reverse the order of the first two elements. The sequence is now: $1,2,3,4$.

In this sequence of operations, Operation $1$ is performed once. It is not possible to sort the sequence with less number of Operation $1$, thus the answer is $1$.

5
10
8
5
3
2

0