UVa 10720 - Graph Construction

// UVa 10720 - Graph Construction
// Erdős–Gallai theorem

#include <iostream>
#include <algorithm>
using namespace std;

bool canRepresentASimpleGraph(int n, int* d) {

	int sumOfDegrees = 0;
	for (int i = 1; i <= n; i++) {
		if (d[i] < 0)
			return false;
		sumOfDegrees += d[i];
	}
	if (sumOfDegrees % 2) {
		return false;
	}

	int left = 0;
	for (int k = 1; k <= n; k++) {

		left += d[k];

		int mid = k * (k - 1);

		int right = 0;
		for (int i = k + 1; i <= n; i++) {
			right += min(d[i], k);
		}

		if (left > mid + right)
			return false;
	}
	return true;
}

int main() {

	while (true) {
		int n;
		cin >> n;
		if (n == 0)
			break;

		int d[10001];
		for (int i = 1; i <= n; i++) {
			cin >> d[i];
		}
		sort(d + 1, d + n + 1, greater<int>());

		if (canRepresentASimpleGraph(n, d)) {
			cout << "Possible" << endl;
		} else {
			cout << "Not possible" << endl;
		}
	}

	return 0;
}