Second Largest Element

Given N integers, print the second largest distinct value in the list.

Duplicates of the largest value do not count as the second largest. In 7 7 5 5 the largest value is 7 and the answer is 5.

The input is guaranteed to contain at least two different values, so an answer always exists.

💡

You can sort the list and walk back from the end until the value changes — or track the best and second-best in a single pass.

Input

Line 1: the integer N. Line 2: N space-separated integers.

Output

A single integer: the second largest distinct value.

Constraints

2 <= N <= 10^5, values between -10^9 and 10^9, and at least two distinct values exist

Example 1

Input

5
3 1 4 1 5

Output

The largest value is 5, so the second largest is 4.

Submit runs your code against 5 test cases — the 1 shown above plus 4 hidden ones covering the awkward cases. Run sample just tries the first example, which is usually what you want while you are still working it out.