[ The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf ]

Every weekend, Germán and Gianina play a football match with their friends. This Saturday, both German and Gianina are injured, so they will participate in the game as coaches.

To choose the teams they will use the following procedure: of the N friends they have in common, each of them is going to pick N/2 players (N is even), with the selection process taking N/2 turns. On every turn, each of them chooses a different player among the ones who have not been selected yet, and this player is assigned to his/her team. Germán won the initial coin flip so he gets to choose first on every turn. However, to be gallant Germán can let Gianina go first on some turns if he wants so.

For example, if N = 6 there are N/2 = 3 turns. Suppose Germán decides to yield his right to choose first on the second and third turns, but not on the first one. In that case, the order of selection of players would be:

Germán - Gianina || Gianina  - Germán || Gianina  - Germán

 Turn 1                        Turn 2                        Turn 3

As we all know, football is a sport ruled by logic. Every friend of Germán and Gianina has a score that indicates how well they play. If the sum of scores of Germán's team is strictly greater than the sum of scores of Gianina's team, then Germán's team will win the match. If the sum of scores is the same for both teams, the match ends in a draw. Otherwise, Gianina's team will be the winner.

Germán wants to be gallant, but he is even more interested in winning the game. Therefore, he wants to yield his turn as many times as possible so that he can still win the game anyway. Gianina also wants to win the game, therefore each time they choose a player they will both do it in a way that maximizes their chances of winning.

Input

The first line contains an integer N representing the number of players to choose from (with 2 ≤ N ≤ 1000 and N even). The second line contains N integers P₁, P₂, ..., P_N representing the scores of each player (1 ≤ P_i ≤ 1000 for i = 1, 2, ..., N).

Output

Print a line containing a single integer that represents how many times Germán can yield his turn in such a way that his team's victory is guaranteed. If Germán can not ensure a victory, you must print the number -1.

Example 1

Input:
6
7 8 2 10 1 4
Output:
1

Example 2

Input:
6
7 8 2 10 1 3
Output:
2

Example 3

Input:
4
60 95 100 65
Output:
0

Example 4

Input:
10
10 10 10 10 10 10 10 10 10 10
Output:
-1