Challenge: Silver Medal

Lab Java Beginner 10 points

Read n race times (smaller is better) and print the time of the second fastest runner. All times are different. Do it in one pass without sorting.

Input

Line 1: n (n ≥ 2). Line 2: n different whole numbers.

Output

The second smallest number.

Example

Input

5
58 49 61 52 70

Output

Sample input available Sample output available

Editor

Java

Hints

Keep two variables: gold (best) and silver (second best).

When a new best arrives, the old gold becomes silver.

Solution explanation

Sorting would be O(n log n). Keeping just the top two while walking once is O(n).

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int gold = Integer.MAX_VALUE, silver = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int t = sc.nextInt();
            if (t < gold) {
                silver = gold;   // old gold drops to silver
                gold = t;
            } else if (t < silver) {
                silver = t;
            }
        }
        System.out.println(silver);
    }
}

Output

Answer