Python All O(1) endpoint algorithm, no amortization
It\'s quite straightforward to get amortized O(logn) with SortedList or amortized O(1) by counting up till the missing video. However, if you are familiar with 
It\'s quite straightforward to get amortized `O(logn)` with `SortedList` or amortized `O(1)` by counting up till the missing `video`. However, if you are familiar with the "endpoint algorithm" that keeps track of all the contiguous segments, it\'s just as simple to get an all `O(1)` algorithm:\n\n1. Use `left` and `right` dictionaries to map the right endpoint to the left endpoint of the segment, and vice versa.\n2. Given a new `video`, check if `video - 1` is in `left`. If it is, `left[video - 1]` will be the new left endpoint instead.\n3. Likewise, if `video + 1` is in `right`, `right[video + 1]` will be the new right endpoint instead.\n4. Finally, return `right[1]` if `1` is in `right`, else `0` for `longest()`.\n\n```\nclass LUPrefix:\n\n    def __init__(self, n: int):\n        self.left = {}\n        self.right = {}\n\n    def upload(self, video: int) -> None:\n        l = self.left.pop(video - 1, video)\n        r = self.right.pop(video + 1, video)\n        self.left[r] = l\n        self.right[l] = r\n\n    def longest(self) -> int:\n        return self.right.get(1, 0)\n```
['Python']