249. Second Largest

Foundation1000 ms256 MBSolved by 0%

Print the second largest DISTINCT value among n integers. If every value is the same, print None.

Distinct matters. In 5 5 4 the answer is 4, not 5, because the two fives are one distinct value.

You can sort and walk backwards, which is O(n log n). You can also do it in one pass with two variables, which is O(n) and is the version worth being able to write: it is the same idea as finding a maximum, with a second slot.

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`

Input

The first line contains an integer n. The second line contains n integers.

Output

Print the second largest distinct value, or None if there is no second distinct value.

Input5 3 1 4 1 5

Output4

Notehas its answer next to the largest value

Input1 1

OutputNone

Noteis a single element, so there is no second distinct value

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution