Problem F
Secret Santa

Ett företag med $N$ avdelningar ska leka leken Secret Santa. Leken går ut på att varje person ska ge en annan person en julklapp, men ingen får reda på vem de ska få en julklapp av. I slutet av leken ska varje person både ha gett och fått exakt en julklapp. För att göra leken mer spännande har företaget bestämt att ingen person får ge en julklapp till någon på sin egen avdelning.

På avdelning $i$ finns det $a_i$ personer. Givet storleken på alla avdelningar, går det att tilldela varje person någon som de ska ge en julklapp så att ingen får en julklapp från någon på sin egen avdelning?

Indata

Den första raden indata består av heltalet $N$ ($2 \leq N \leq 10^5$), antalet avdelningar på företaget.

Den andra raden innehåller $N$ heltal $a_i$ ($0 \leq i < N, 1 \leq a_i \leq 10^9$), där $a_i$ är antalet personer som arbetar på avdelningen med index $i$.

Utdata

Skriv ut ”Ja” om det går att leka Secret Santa så att ingen får en julklapp av någon på sin egen avdelning. Skriv ut ”Nej” annars.

Poängsättning

Din lösning kommer att testas på två olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av Exempelfall

I andra exempelfallet finns det två avdelningar med storlekarna $1$ och $2$. Det går inte att tilldela varje person en julklappsgivare från en annan avdelning. Svaret är därför ”Nej”.

I tredje exempelfallet finns det fyra avdelningar med storlekarna $2$, $1$, $2$ och $5$. En möjlig tilldelning är att låta de två personerna på avdelning $1$ ge julklappar till två av personerna på avdelning $4$, personen på avdelning $2$ ge en julklapp till en tredje person på avdelning $4$, de två personerna på avdelning $3$ ge julklappar till de två sista personerna på avdelning $4$, och slutligen låta de fem personerna på avdelning $4$ ge julklappar till de två personerna på avdelning $1$, personen på avdelning $2$ och de två personerna på avdelning $3$. Svaret är därför ”Ja”.

Figure 1: En möjlig tilldelning av personerna i exempelfall $1$.

3
2 1 1

Ja

2
1 2

Nej

4
2 1 2 5

Ja

5
2 1 2 3 6

Ja