Jamie has recently joined the Adelaide Competitive Programming Club, and everyone knows that he does not have much aura. In order to increase his aura and impress the executives, Saadan tells him to play a game called Stone Moving.

Stone Moving is a game in which several stones are placed at different positions on a line. The objective of the game is to move all the stones so that they end up at the same position.

In a given move, Jamie can move a stone either to the left or to the right by at most 2 positions from its current location.

However, Jamie soon discovers that he has been betrayed by Saadan. In this version of the game, Jamie can only lose aura, so he must try to minimise his aura loss.

If he moves a stone 1 position to the left or right, he loses 1 aura as moving only one position is frowned upon.

If he moves a stone 2 positions to the left or right, he loses no aura at all.

Jamie wants to know the minimum amount of aura he will lose in order to move all the stones to the same position.

Input

The first line contains an integer ~n~ (~1 \le n \le 10^6~), representing the number of stones in the game.

The second line contains ~n~ integers ~x_i~ (~-10^9 \le x_i \le 10^9~), representing the position of a stone.

Output

Output the minimum amount of aura that Jamie can loose while playing the game.

Example

Input 1

3
6 3 8

Output 1

1

Jamie decides to move all the stones to position 6:

• Stone 1 stays the same
• Stone 2: 3 -> 4 -> 6, loses one aura
• Stone 3: 8 -> 6, loses no aura

Input 2

4
1 2 3 4

Output 2

2

Moving 1 to 3 loses no aura, while moving 2 and 4 to 3 lose one aura each.

Input 3

5
5 5 5 5 5

Output 3

0

The stones are already in the same position.