Loss of novelty while under review
I would respond to the editor that:

Our paper was submitted on DATE.  Paper A was published on DATE.  Both works show that XYZ.  The publication of A in the well-known Journal of W is evidence that our work is important.

Most editors are decent people and will realize that the prior publication of A is not within your control, nor is it something you overlooked.
Do revise your manuscript to clearly compare your work with A.  In the manuscript, you can state that the paper A was published after your initial submission, if you wish.
Publishing multiple papers that independently get the same result is good for science and should be rewarded with publication.