TAP2014G - Gallantry

[ 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 P1, P2 ... PN representing the scores of each player (1 ≤ Pi ≤ 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.

Examples

Input:
6
7 8 2 10 1 4

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

Output:
2
Input:
4
60 95 100 65

Output:
0
Input:
10
10 10 10 10 10 10 10 10 10 10

Output:
-1

Added by:Fidel Schaposnik
Date:2014-09-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2014

hide comments
2017-06-02 03:33:46
Hi, i trying to solve this problem with Python 3.5 and i have the output of the judge: "runtime error (NZEC)". Any suggestion?
2016-10-30 07:52:04
fantastic math problem :D
2015-01-08 06:31:43 kelaseek
before submitting take a look at @fidel's comment
2014-10-04 20:46:28 Secret Agent
@fidel thats not the issue..its passing first 28 judges..can anyone give me some tricky test case?

[reply by cyclops: The judge runs all data sets and only tells you the result afterward. You probably failed on an early test file.]

Last edit: 2014-10-04 22:05:30
2014-10-03 16:15:36 Fidel Schaposnik
@Secret Agent: no newline at the end of the line ;-)
2014-10-03 08:19:29 Secret Agent
failing on 28th judge..any suggestions?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.