Soccer Game

Time limit2sMemory limit512 MB

Summary

Given n teams and their reported win counts in a round-robin with no ties, decide if some set of match results produces exactly those scores.

Level: Medium5 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

A soccer league has $n$ teams. Every team plays every other team exactly once, so each team plays $n - 1$ matches. There are no draws, because a tied match is decided by a penalty shootout. The winner of a match gets 1 point and the loser gets 0 points.

Once the schedule is over, every team reports its own total to the league office. The office wants to be sure that no team made a mistake. In other words, it wants to decide whether some set of match results that obeys the league rules gives every team exactly the total it reported.

Given the $n$ reported totals, write a program that decides whether they are valid.

Input

The program reads from standard input. The input has two lines. The first line contains the number of teams $n$ ( $2 \le n \le 10000$ ). The second line contains the $n$ reported totals, separated by spaces. Each total is an integer between $0$ and $n - 1$ , inclusive.

Output

The program writes to standard output. Print 1 if the reported totals are valid, and -1 otherwise.

Examples4

Example 1
Input
```
4
0 2 1 3
```
Expected output
```
1
```
Example 2
Input
```
4
3 3 0 0
```
Expected output
```
-1
```
Example 3
Input
```
2
0 1
```
Expected output
```
1
```
Example 4
Input
```
3
1 1 1
```
Expected output
```
1
```