Find Minimum Replacements

You may choose any two drones from capacities 1..10^9, and the two capacities must differ; they deliver packages alternately (the first drone delivers packages 1, 3, 5, ...). A package is fine if its weight does not exceed the capacity of the drone used; you may replace the weights of some packages with any positive integers, and the number of replacements should be minimized. Note that it is not required that the packages delivered by the same drone have equal weights.

输入格式

The first line contains n, and the second line contains the package weights. This site sets 1≤n≤100000 and package weights in 1..10^9.

输出格式

Output a single integer answer.

样例 1

输入：

4
1 2 3 4

输出：

0

样例 2

输入：

2
1000000000 1000000000

输出：

1

样例 3

输入：

4
1000000000 1 1000000000 1

输出：

0

样例说明

Example 1: choosing the two largest capacities is enough for everything, so no replacement is needed. Example 2: both positions need the largest capacity, but the two drones differ, so 1 package is replaced. Example 3: the large drone delivers the odd positions and the small drone the even positions, so 0 packages.