Price Drop Alerts

A price tracker stores a product's price for each day, and prices[i] is the price on day i in cents. On each day, the recent high is the highest price over the previous k days (days i - k to i - 1), or over all the previous days when there are fewer than k of them. Day 0 has no previous days, so it never raises an alert.

Write price_drops(prices, k, percent) that returns a list of the days on which the price is at least percent percent below the recent high, in order. In other words, day i alerts when prices[i] <= high * (100 - percent) / 100.

Examples

price_drops([1000, 990, 1200, 1050, 1080, 900, 990], 3, 10)  # returns [3, 4, 5]

On day 4 the recent high is 1200 (day 2), and 1080 is exactly 10% below it, so it counts. By day 6 the 1200 is more than 3 days back: the recent high is 1080, and 990 is not 10% below that.

Constraints

• 0 <= len(prices) <= 200000 and 1 <= k <= 200000
• 1 <= percent <= 99, and prices are whole numbers from 1 to 1,000,000.

Note

Compare with whole numbers, prices[i] * 100 <= high * (100 - percent). Floating point can be off right at the boundary: 1000 * (1 - 7 / 100) gives 929.9999999999999, not 930.