Make sure we always remove duplicates before inserting
Otherwise we may introduce such duplicates on some code paths.
BUG: 393484