//-------------------------------------------------------------
// Check the given list can be a degree list of some graph
//   O(n^2)  (I suspect it can be made faster, though...)
//
// Verified by
//   - SRM 398 Div1 LV3
//
//((
// Havel-Hakimi
//   If G[0], ..., G[n] (decreasing) is graphical,
//   then G[1]-1, G[2]-1, ..., G[G[0]]-1, G[G[0]+1], .., G[n]
//   is also graphical.
//))
//-------------------------------------------------------------

bool isGraphical( vector<int> G )
{
	sort( G.begin(), G.end() );

	vector<int>::iterator b = lower_bound( G.begin(), G.end(), 1 );
	vector<int>::iterator e = G.end();

	while( b < e )
	{
		int n = *(--e);
		if( e-b < n )
			return false;
		for(vector<int>::iterator i=e-n; i!=e; ++i)
			--*i;
		inplace_merge( b, e-n, e );
		b = lower_bound( G.begin(), G.end(), 1 );
	}
	return true;
}
