Most modern democracies select the government somewhat indirectly.
The UK votes in 650 (currently, the number changes over time) separate constituencies each selecting a single MP by a first past the post method. Those MPs then select a government. The USA votes for the next president not directly but via an electoral college which usually allocates all the electoral college votes to the candidate with a majority of votes in the state.
Both the UK and USA can, therefore, have a winner who did not win the aggregate popular vote across the whole country (for example, Trump won the electoral college with ~3m fewer votes overall than Clinton). This is an inherent quirk in indirect systems of selecting governments (or presidents).
Is this quirk common? How often in long standing representative democracies does the "winner" not also win the popular vote?
Note: There are many voting systems where the question may be meaningless. For example, countries like Ireland who use STV give people multiple votes (so it may be impossible to say who "won" the vote. Others have proportional parliamentary systems where the quirk in systems like the UK is designed out. The scope of the question, therefore, excludes those countries where it doesn't make sense. So answers should explain the nature of the electoral system they refer to. I'm not restricting it to specific countries as I don't know enough about every system to be sure I've picked the ones where it does apply. So consider it in two parts: which systems have the quirk and how common is it in practice.