Choose a model call timeout from past latencies

Most of your agent's model calls return in 1 or 2 seconds, but a few hang for a minute. Abandoning a slow call and trying again often finishes sooner than waiting it out. You have the latencies of past calls and want the timeout that makes a call finish soonest on average.

Write best_timeout(latencies, retry_gap) that returns that timeout in milliseconds.

Input and output:

• latencies: 1 to 100,000 past latencies in milliseconds, each a whole number from 1 to 100,000.
• retry_gap: the milliseconds the agent waits after abandoning an attempt before it starts the next one, 0 to 100,000.
• Return a whole number of milliseconds.

Rules:

• Each attempt takes a latency picked at random from latencies, every entry equally likely, independently of every other attempt.
• With timeout T, an attempt whose latency is at most T succeeds, and the call is done. Otherwise the agent abandons the attempt after T milliseconds, waits retry_gap milliseconds, and starts a new attempt. It keeps going until an attempt succeeds.
• The expected time is the average, over every way the attempts can turn out, of the time from the start of the first attempt until one succeeds.
• Return the whole number T, 1 or more, with the smallest expected time. If several values tie, return the smallest of them.