Rust, HashSet, O(n)
Only record the current end of the prefix [1..i].  Keep extending it while can be extended.\n\nuse std::collections::HashSet;\n\nstruct LUPrefix {\n    points: 
Only record the current end of the prefix [1..i].  Keep extending it while can be extended.\n```\nuse std::collections::HashSet;\n\nstruct LUPrefix {\n    points: HashSet<i32>,\n    far: i32,\n}\n\n\n/** \n * `&self` means the method takes an immutable reference.\n * If you need a mutable reference, change it to `&mut self` instead.\n */\nimpl LUPrefix {\n\n    fn new(n: i32) -> Self {\n        Self {\n            points: HashSet::new(),\n            far: 0\n        }\n    }\n    \n    fn upload(&mut self, video: i32) {\n        self.points.insert(video);\n        while self.points.len() > 0 {\n            let post = self.far + 1;\n            if self.points.contains(&post) {\n                self.far += 1;\n                self.points.remove(&post);\n            } else {\n                break;\n            }\n        }\n    }\n    \n    fn longest(&self) -> i32 {\n        self.far\n    }\n}\n```
['Rust']