/**
 * www.algorytm.org
 * algorytm testowania czy podany ciąg 
 * stopni wierzcholków grafów jest graficzny
 * Tomasz Lubiński (c) 2005
 */
public class Graficzny1 {
	
	private static int  c[];

	public static void main(String[] args) {
		int  flag, graficzny;
		int  n,i,j,smin,s;
		
		// pobierz dane
		System.out.println("Podaj liczbe wierzcholkow grafu");
		n = Console.readInt("?");
		c = new int[n];
		for (i=0; i<n; i++) {
			c[i] = Console.readInt("Podaj stopien wierzcholka " + (i+1));
        }
		
		// algorytm testowania czy podany ciąg stopni wierzcholkow jest graficzny
		graficzny = 1;
		
		// sprawdz czy suma ciągu jest liczbą parzystą
		s=0;
		for (i=0; i<n; i++) 
			s+=c[i];
		if ((s%2)!=0)
		        graficzny = 0;
		//posortuj ciąg nierosnąco jeżeli suma jest liczbą parzystą		
		else {
			flag=1;
			while (flag==1) {
				flag=0;
				for (i=0; i<n-1; i++)
					if (c[i]<c[i+1]) {
						s=c[i];
						c[i]=c[i+1];
						c[i+1]=s;
						flag=1;
					}
			}
		}
		
		//	sprawdz czy spelniona jest nierownosc P. Erdos, T. Gallai (1960)
		j=0;
		while ((graficzny==1) && (j<n-1)) {
			s=0;
			for (i=0; i<=j; i++) 
				s+=c[i];
			smin=0;
			for (i=0; i<n; i++)
				if ((j+1)<c[i]) 
					smin=smin+(j+1);
				else 
					smin+=c[i];
		        if (s>(j*(j+1)+smin)) 
		        	graficzny=0;
		        else
		        	j++;
		}
		
		// podaj użytkownikowi wynik
		if (graficzny == 1) 
			System.out.println("Podany ciąg jest graficzny");
		else 
			System.out.println("Podany ciąg nie jest graficzny");
	}
}