How to organize a data structure for storing a list of users?

Question

Data Structures

I'm trying to find an efficient structure for working with data.
Conditions
The structure stores data in the following format:

• id: int
• ts: date/int

The following operations are defined for the structure:
* update(id, new_ts) - change the ts of the record with id = id.
* delete(ts_max) - delete records with ts < ts_min *
latest(ts_min) - get a list of records (or id) with ts >
ts_min
ts values ​​in the structure:
* delete - absent
The number of update and latest operations will have approximately the same order, so none can be neglected.
And now the Question:
I can't think of a way to meet all the operations at the same time within a reasonable time. < O(N) is considered reasonable.
I do not rule out that I'm just stupid - and therefore I will be glad not only for advice, but also for criticism.
Language - in case it matters, python.

Answer 1

For ts you make a binary tree, for id - a dictionary. In a tree, leaves can be references to objects in a dictionary or vice versa, it doesn't matter.
In this case, by id - the operation will be linear, by tree - log (n)

Answer 2

In a particular case, it seems like it turned out to be reduced to the "doubly linked list + dictionary" option.
In the general case, the question remains open.
UPD: A bit late. @xytop thanks.