K-th largest value over the last N seconds of a stream

Start with finding the k-th largest element of an array. Then values arrive with timestamps and queries ask for the k-th largest among values from the last N seconds; design a structure that handles inserts, expiry and queries efficiently.