Second Largest Element

Array

Given an array of integers, find the second largest element in the array. The array will have at least two different elements.

Example 1

Input

[
  10,
  5,
  4,
  8,
  20
]

Output

Explanation. The largest element is 20 and the second largest is 10.

Example 2

Input

Output

Explanation. Ignoring the repeated largest element 25, the second largest is 16.

Example 3

Input

[
  -1,
  -2,
  -3,
  -4
]

Output

-2

Explanation. The largest element is -1 and the second largest is -2.

Follow-up: What would be the approach to solve this problem with a single traversal?

Constraints:

The input array will have at least two elements and all the elements will be integers.