Home

Problem Statement

Snuke got an integer sequence of length $N$ from his mother, as a birthday present. The $i$-th $(1 ≦ i ≦ 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 ≦ N ≦ 10^5$
• $0 ≦ A_i ≦ 10^9$
• If $i ≠ j$, then $A_i ≠ A_j$.
• All input values are integers.

Sample Input 1

4
2
4
3
1

Sample Output 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$.

Sample Input 2

5
10
8
5
3
2

Sample Output 2

0