The Removed Item

A packing list original was shuffled and exactly one item was removed, giving shuffled. Items can repeat, so a plain set is not enough. Return the removed item.

Examples

Input:  original = [4, 4, 7, 1], shuffled = [1, 4, 7]
Output: 4

Input:  original = [9], shuffled = []
Output: 9

Constraints

• 1 <= len(original) <= 10**5, len(shuffled) == len(original) - 1
• shuffled is a permutation of original with one element removed.
• Target complexity: O(n) time.

Goals

• Handle duplicates that a plain set would lose
• Find the one count that disagrees