Given the marks of n students, print the second-highest distinct mark. If all marks are equal, print NONE.
Write it in Java in a single pass without sorting, and be careful with the starting values of your trackers (marks can be negative here).
Constraints
- 1 ≤ n ≤ 100000
- −10^9 ≤ mark ≤ 10^9
Input and output
- Input
- Line 1: n. Line 2: n integers.
- Output
- One integer, or `NONE`.
Examples
Input 1
5
72 91 85 91 60Output
8591 is the highest (it appears twice); the next distinct mark is 85.
Input 2
3
50 50 50Output
NONEOnly one distinct mark, so NONE.
Show hints
- Track the largest and the second largest seen so far.
- Skip values equal to the current largest so duplicates do not count twice.
Show the explanation
Keep first and second, both "unset" at the start (in Java, use Long.MIN_VALUE with a flag, or a nullable Long; starting at 0 breaks on negative input). For each value: if it is greater than first, shift first down into second; else if it is strictly between second and first, it becomes the new second; values equal to first are ignored. One pass, O(1) space. Sorting works too but costs O(n log n).
Original UniCircle question. Last reviewed 22 Oct 2026.