Stamps for Every Postage

You have a box of stamps, and stamps lists their values in cents, sorted from smallest to largest (values can repeat). A parcel can carry any number of your stamps, but each stamp can only be used once. You want to be able to pay every postage from 1 cent up to n cents exactly, using some of your stamps.

You may buy extra stamps of any values you like. Write fewest_extra(stamps, n) that returns the smallest number of stamps you need to buy.

Examples

fewest_extra([1, 4], 7)          # returns 1
fewest_extra([2, 9], 30)         # returns 4
fewest_extra([1, 1, 2, 5], 9)    # returns 0

With [1, 4] you can pay 1, 4 and 5 cents but not 2 or 3. After buying a 2-cent stamp every postage from 1 to 7 works: 1, 2, 2 + 1, 4, 4 + 1, 4 + 2 and 4 + 2 + 1.

Constraints

• 0 <= len(stamps) <= 100,000
• 1 <= stamps[i] <= 10^9, sorted from smallest to largest
• 1 <= n <= 10^18

Note

n can be enormous, so checking the postages one at a time is out of the question.