How can I get into the palace?

Hint 1 of 2:

The guards seem to fight an awful lot over their wives.