Challenge: Personal Bests

Lab Java Beginner 10 points

An athlete records n jump distances in order. Print how many times they set a new personal best (a jump longer than every earlier one; the first jump always counts), then the list of those records.

Input

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

Output

Line 1: the number of records. Line 2: the record jumps, separated by spaces.

Example

Input

7
5 3 6 6 9 2 10

Output

4
5 6 9 10

Sample input available Sample output available

Editor

Java

Hints

Keep best = the longest jump so far.

You don't know how many records there will be, so an ArrayList (it grows) is handy.

Solution explanation

One pass, and add at the end is O(1) on average, so the whole thing is O(n).

Show solution

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> records = new ArrayList<Integer>();
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int jump = sc.nextInt();
            if (jump > best) {
                best = jump;
                records.add(jump);
            }
        }
        System.out.println(records.size());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < records.size(); i++) {
            if (i > 0) sb.append(' ');
            sb.append(records.get(i));
        }
        System.out.println(sb);
    }
}

Output

Answer