Calling Up the Price of a Rowing Boat

At a harbour sale an auctioneer sells an old rowing boat by calling out rising prices, in whole dollars. Bidder i values the boat at values[i] dollars and stays in the bidding at a called price p exactly when values[i] >= p (they would still be happy to pay p). The rules:

1. The auctioneer first calls start. If nobody stays in at start, the boat is not sold.
2. Whenever only one bidder stays in at the current price, the boat is sold to that bidder at that price.
3. Whenever two or more bidders stay in at the current price p, the auctioneer calls p + step:
   • if at least one bidder stays in at p + step, the bidding goes on from p + step with those bidders;
   • if nobody stays in at p + step, the boat is sold at p to the bidder with the smallest index among those who stayed in at p.

Write english_auction(values, start, step) that returns the tuple (winner, price, gap), where gap = price - second and second is the second-highest number in values (counting repeats: in [64, 64, 30] it is 64). If the boat is not sold, return (None, None, None).

Examples

Input:  values = [70, 95, 88], start = 10, step = 5
Output: (1, 90, 2)
Explanation: at 85 bidders 1 and 2 stay in; at 90 only bidder 1 (95 >= 90 > 88).
The second-highest value is 88, so the gap is 2.

Input:  values = [64, 64, 30], start = 20, step = 10
Output: (0, 60, -4)
Explanation: at 60 bidders 0 and 1 stay in, at 70 nobody: bidder 0 buys at 60.

Input:  values = [100, 30], start = 50, step = 7
Output: (0, 50, 20)
Explanation: only bidder 0 stays in at the opening price.

Goals

• Simulate an ascending auction round by round from its stated rules
• Apply the rule for a sale when every remaining bidder drops out at once
• Compare the final price with the second-highest value and see the role of the increment