Dynamic Convex Hulls under Window-Sliding Updates

We consider the problem of dynamically maintaining the convex hull of a set $S$ of points in the plane under the following special sequence of insertions and deletions (called window-sliding updates): insert a point to the right of all points of $S$ and delete the leftmost point of $S$. We propose an $O(|S|)$-space data structure that can handle each update in $O(1)$ amortized time, such that all standard binary-search-based queries on the convex hull of $S$ can be answered in $O(\log |S|)$ time, and the convex hull itself can be output in time linear in the number of its vertices.