A cheeky way to do it is this, reuse the randomness that we are assuming about the input data:

1. Data structure in pseudo code:

    max = 0
    items = []
    def add(x: int32):
       max = max(x, max)
       items.push(x)

2. Algorithm:

    def doit()
        if max == int32.max return 0
        sleep (1000)
        return 0

As you add items to this data structure, on average over all possible data inputs the time taken for doit() will tend from K+1000ms to a constant K.